получить индексы n самых маленьких элементов в массиве

Question

У меня есть массив int int[] myArray = new int[100];, и я хочу получить индексы наименьших 10 (любых n) элементов. Как я могу это сделать?

Answer 1

Сортировать массив и затем выбрать 10 просто, но это будет O (n log n), и если вы не хотите переупорядочивать исходный массив, вам также нужно будет сделать копию.

Лучшей идеей является использование max-heap (или очереди приоритетов), которая автоматически сортирует элементы по мере их вставки, так что самый большой элемент - это корневой узел. Идите вдоль массива, продолжайте вставлять элементы, пока не достигнете 10; затем для каждого последующего элемента просто проверьте, меньше ли он самого большого элемента в куче (проверка с постоянным временем), и, если это так, вытащите этот элемент и вставьте новый элемент. Когда вы прошли весь массив, 10 вещей, оставшихся внутри, являются вашими минимальными элементами. Это даст вам ваш результат в O (n log 10) == O (n), поскольку каждая вставка в кучу будет стоить только O (log 10).

Реализация Java Priority Queue по умолчанию является минимальной очередью, поэтому вам нужно будет передать Comparator, который меняет порядок. См. этот вопрос для примеров того, как это сделать. Вам нужно создать пользовательский объект, который также содержит пары (значение, индекс), если вы хотите получить индексы в конце.

Answer 2

создайте объект, который содержит номер и индекс, затем создайте массив из этих объектов, затем выполните Array.Sort (arrayset [], компаратор) java docs . Затем вы можете просто выбрать верхние элементы x из отсортированного массива.

EDIT: Примерно так ... [Я использовал это для сортировки по 'расстоянию'

import java.util.Arrays;
import java.util.Comparator;

public class NearestObject
{
    public NearestObject(int position, int distance)
    {
         this.Position = position;
         this.Distance = distance;
    }
    public int Position = 0;
    public int Distance = 0;

    public static NearestObject[] SortDistance(NearestObject[] items)
    {
        Arrays.sort(items, new DistanceSort());
        return items;
    }

}

class DistanceSort implements Comparator<NearestObject>
{
    public int compare(NearestObject o1, NearestObject o2)
    {
        return o1.Distance - o2.Distance;
    }
}

Answer 3

Прямое решение состоит в том, чтобы перебрать массив и вести список из n наименьших найденных элементов и их индексов. Это решение O (N) и приемлемо в большинстве случаев. Я предполагаю, однако, что это домашнее задание, и вы должны иметь что-то лучше, чем O (N).

Answer 4

Сортируйте их по индексу и верните первые 10

Сначала создайте структуру для хранения и индекса, и значения:

class IndexValue {
   final int i;
   final int v;
}

Затем создайте массив с этой новой структурой:

IndexValue[] array = new IndexValue[myArray.length];
for( int i = 0 ; i < array.length ; i++ ) {
    array[i] = new IndexValue( i, myArray[i] );
}

Наконец-то отсортируйте его и возьмите первые N элементов

Arrays.sort( array ); // you'll need to implement Comparator though 

for( int i = 0 ; i< 10 ;i++ ) {
    System.out.print( array[i] );
}

Вот полный рабочий код:

import java.util.Arrays;
import java.util.Random;
import java.util.Comparator;
import static java.lang.System.out;

class IndexValue {
   final int i,v;

   public IndexValue( int i, int v ) {
       this.i = i;
       this.v = v;
   }
}
public class SortByIndex {
    public static void main( String [] args ) {

        Random random = new Random();

        int [] myArray = new int[100];
        IndexValue[] array = new IndexValue[myArray.length];

        // Fill the array 
        for( int i = 0 ; i < 100; i++ ) {
            myArray[i] = random.nextInt();
            array[i] = new IndexValue( i, myArray[i] );
        }

        // Sort it 
        Arrays.sort( array, new Comparator<IndexValue>(){
            public int compare( IndexValue a, IndexValue b ){
                return a.v - b.v;
            }
        });

        // Print it
        out.println("Top:");
        for( int i = 0 ; i < 10 ; i++ ) {
            out.println( String.format("array[%d]=%d",  array[i].i, array[i].v ));
        }

    }
}

Answer 5

Если вы ищете практический ответ (в отличие от фактического алгоритма сортировки и т. Д.), Просто используйте HashMap или PriorityQueue. Если скорость не имеет значения, попробуйте это легко. Это проще, чем PriorityQueue, так как вам не нужен пользовательский объект:

HashMap<Integer, ArrayList<Integer>> indexMap = new HashMap<Integer, ArrayList<Integer>>();

Заполните indexMap, чтобы мы могли получить индексы для любого заданного числа в массиве

for (int index = 0; index <= array.size; index++) {
   if (indexMap.get(array[index]) == null) { // Prime it with an ArrayList
      indexMap.put(array[index], new ArrayList<Integer>());
   }

   indexMap.get(array[index]).add(index);
}

Для наименьших n чисел в массиве выведите их индекс.

Arrays.sort(array);
for (int index = 0; index <= n; index++) {
   System.out.println(indexMap.get(array[index]).remove(0));
}

Answer 6

Вы можете отсортировать массив, зациклить первые 10 элементов, а затем для каждого элемента искать в массиве, какую позицию он занимает ... возможно, это не самый эффективный способ, но он проще.