Как построить массив индексов, которые представляют значения разных массивов от самого высокого до самого низкого?

Question

Название может быть немного запутанным, так что вот пример. У меня есть два массива:

int [] scores;
scores = new int[5];  //(5,7,10,3,6)
int [] places;
places = new int[5];  //(1,2,3,4,5)

Мне нужно как-то отсортировать второй массив (я не могу изменить первый), чтобы он представлял количество элементов в первом массиве. 10 - самое высокое, поэтому его место должно быть 1-м, 3 - самым низким, поэтому его место должно быть 5-м.

После сортировки второй массив должен выглядеть следующим образом:

places = {4,2,1,5,3};

Вотмой код, и мне нужна помощь, чтобы он работал так, как должен.

do {
    for (int i = 0; i < 5; i++) {
        for (int j = 1; j < 5; j++) {
            if (scores[i] < scores[j]) {
                temp = places[i];
                places[i] = places[j];
                places[j] = temp;
                flag = true;
            } else {
                flag = false;
            }
        }
    }
} while (flag);

Заранее спасибо

Answer 1

@ Корашен посоветовал довольно хорошее решение,

Другой способ: предположим, что все значения баллов различны и положительны, вы можете сделать копию массива, отсортировать его и вычесть, чтобы узнать индексы,

в вашем примере:

до сортировки: scores = (5,7,10,3,6)

после сортировки: scores_sorted = (3,5,6,7,10)

значение мест будет следующимправило:

if(scores_sorted[i]-scores[j] == 0) places[i] = j

полный пример:

int[] scores = new int[]{5, 7, 10, 3, 6};
int[] scores_sorted = scores.clone();
int[] places = new int[]{0,1,2,3,4};
sort(scores_sorted);
for(int i=0;i<5;++i){
    for(int j=0;j<5;++j){
        if(scores_sorted[i]-scores[j] == 0){
             places[i] = j;
          }
     }
}

Answer 2

Вы можете использовать любой алгоритм сортировки над places, но вместо сравнения places сравните scores, индексированный как places.

Вот модифицированный quickSort:

static int partition(int[] iarray, int[] varray, int begin, int end) {
    int pivot = end;

    int counter = begin;
    for (int i = begin; i < end; i++) {
        if (varray[iarray[i]] < varray[iarray[pivot]]) {
            int temp = iarray[counter];
            iarray[counter] = iarray[i];
            iarray[i] = temp;
            counter++;
        }
    }
    int temp = iarray[pivot];
    iarray[pivot] = iarray[counter];
    iarray[counter] = temp;

    return counter;
}

public static void quickSort(int[] iarray, int[] varray, int begin, int end) {
    if (end <= begin) return;
    int pivot = partition(iarray, varray, begin, end);
    quickSort(iarray, varray, begin, pivot - 1);
    quickSort(iarray, varray, pivot + 1, end);
}

Единственное изменение - добавить аргумент varray и сравнение iarray[i] < iarray[pivot] с varray[iarray[i]] < varray[iarray[pivot]].

ПРИМЕЧАНИЕ: места должны быть числами от 0в n - 1.

Если places являются ключами вместо индексов, вам необходим промежуточный Map для преобразования varray[iarray[i]] в varray[real_index_of.get(iarray[i])].

Примером работы может быть:

int[] scores = new int[]{5, 7, 10, 3, 6};
int[] places = new int[]{0, 1, 2, 3, 4};
quickSort(places, scores, 0, places.length - 1);
System.out.println(Arrays.stream(scores).mapToObj(Integer::toString).collect(joining(", ")));
System.out.println(Arrays.stream(places).mapToObj(Integer::toString).collect(joining(", ")));

С выводом:

5, 7, 10, 3, 6
3, 0, 4, 1, 2

(ваш вывод неверен, поскольку 5 является вторым наименьшим значением)