Как получить исходный индекс элемента k min

Question

У меня есть массив вроде {40,78,56,98,1, -9}, и размер этого массива может быть огромным. Я хочу получить индекс первого элемента K min. Я могу использовать min-heap / priority-queue, чтобы получить элементы K min за очень хорошее время. Но я не знаю, как я могу получить их индекс. Пожалуйста, объясните мне, как я могу решить мою проблему.

Я пытался использовать TreeMap, чтобы получить то же самое, но это занимает слишком много времени, если массив увеличивается.

Пример вход: {40,78,56,98,1, -9}, К = 2 вывод: {5,4}

Answer 1

Если вам разрешено использовать приоритетную очередь, вы можете добавить значение, а также индекс в приоритетную очередь, создав класс Pair и передав компаратор при инициализации приоритетной очереди.Класс Pair может быть следующим:

class Pair {
    Pair(int val, int idx){
        this.val = val;
        this.idx = idx;
    }
    int val;
    int idx;
}

1. Вы можете создать максимальную кучу и добавить в нее первые k элементов.
2. Обойти массивот (k + 1)-го элемента.
3. Проверьте, не меньше ли элемент max (то есть является корнем кучи), чем (k + 1) th element, если он меньше, чем удалить элемент max и добавить новый элемент в кучу, создав новый объект Pair.
4. Выполнить Шаг 3 до достижения конца массива.

Вы можете инициализировать очередь приоритетов, как показано ниже:

Queue<Pair> maxHeap = new PriorityQueue<>(k, (pair1, pair2) -> -Integer.compare(pair1.val, pair2.val));

Answer 2

ОК, я предполагаю, что вы хотите что-то вроде следующего: Получить индексы первых 2 минутных элементов данного массива. Это может быть достигнуто следующим образом:

 int[] array = {5,75,73,4,78,6,4,3,4,3,64};
 // stream the array of integers, box them, sort them by comparing values of their indexes, unbox them, limit only first 2 and get them to array.
 int[] getIndexes = IntStream.range(0, array.length).boxed().sorted(Comparator.comparing(i -> array[i])).mapToInt(i->i).limit(2).toArray();