Cho một mảng số nguyên arr có size n, n > 0. Tìm thứ hạng của từng phần tử trong mảng. Đối xuất hiện các phần tử bị lặp lạị thì thứ hạng của chúng được tính bằng cách tính trung bình cộng thứ hạng của chúng.
Ví dụ
Input: arr[] = {1, 2, 3}
Output: 2.0 3.0 1.0
Input: arr[] = {10, 12, 15, 12, 10, 25, 12}
Output: 1.5, 4.0, 6.0, 4.0, 1.5, 7.0, 4.0
Mảng sau khi được sắp xếp sẽ là arr[] = {10, 10, 12, 12, 12, 15, 25}
Chúng ta thấy 10 là số nhỏ nhất trong mảng, nên 10 là được sắp ở vị trí 1 và 2 => trung bình 1 + 2 / 2 = 1.5.
Với 12 là số tiếp theo nằm ở vị trí 3, 4 và 5 =? (3 + 4 + 5) / 3 = 4.0 các số khác tương tự
Chúng ta để ý một xíu, mỗi phần tử trong mảng chúng ta cần biết 2 thông số để tính ra được thứ hạng của nó trong mảng đó là: số lần xuất hiện(count) và thứ hạng đầu tiên (r)
Ví dụ với input trên số 10 xuất hiện 2 lần và r = 1.
Công thức là: (r + r + 1+ r + 2 + … + r + count – 1)/ count (1)
Chúng ta nhớ dãy số: 1 + 2 + 3 + … + n = n(n+ 1)/2
(1) sẽ được viết lại: (r*s + 1 + 2 + 3 + … + s-1)/s
<=> (r*s + (s – 1)(s – 1 + 1)/2)/s
<=> r + s-1/2
Vậy với mỗi số chúng ta sẽ sử dụng 2 vòng lặp để tìm ra số lần nó xuất hiện trong mảng và thứ hạng đầu tiên mà nó có được rồi áp dụng công thức trên là xong nhé anh em.
import java.util.Arrays;
public class Main {
public static void rankAllElement(int[] arr, int n) {
for (int i = 0; i < n; i++) {
float count = 1, r = 1;
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j] && i != j) {
count++;
} else if (arr[i] > arr[j]) {
r++;
}
}
System.out.print((r + 0.5*(count - 1)) + " ");
}
}
public static void main(String[] args) {
int arr[] = {10, 12, 15, 12, 10, 25, 12};
rankAllElement(arr, arr.length);
}
}
Output: 1.5 4.0 6.0 4.0 1.5 7.0 4.0
Độ phức tạp: O(n^2)
Link đề: https://www.geeksforgeeks.org/rank-elements-array/