如何打印数组中10个最小值的索引

Question

我需要从一个包含 2,000 个元素的数组中选出最小的10个数字，并打印它们的索引。

一开始我尝试对这个数组进行排序，然后打印值为array[0到9]中的最小数字。虽然这是最小的数字，但我却失去了这些值在未排序数组中所拥有的索引。

第二种方法是尝试使用TreeMap，这个方法很有效，但当我有两个相等的键时，它只会打印其中的一个，而我却希望打印它们两个。

以下是使用TreeMap的代码示例:

  TreeMap<Integer, String> treemap = new TreeMap<Integer, String>();

  treemap.put(2, "two");
  treemap.put(1, "one");
  treemap.put(3, "three");
  treemap.put(6, "six");
  treemap.put(6, "six2");
  treemap.put(5, "five");      

  Collection<String> coll=treemap.values();
  System.out.println("Value of the collection: "+coll);  

到目前为止，我还没有使用过treeMap，所以可能存在一些简单的方法来解决它。或者使用其他东西会更好吗？

我将非常感激任何帮助。

- Petr Šrámek

---

问题是“打印10个最小值的索引”（可能会有一些相同值的索引未被打印），还是“打印10个最小值的索引”（可能超过10个，甚至整个数组如果只有10个或更少不同的值）？ - hyde

没错。谢谢你给主题取了个更好的名字 :) - Petr Šrámek

Answer 1

这些数值非常小，但我失去了它们在未排序数组中的索引。

那么为什么不创建一个类来保存这些索引呢？然后按值对数组进行排序，您就可以获得相关联的索引了。

class MyClass implements Comparable<MyClass>{
    private int index;
    private int value;

    public MyClass(int i, int v){
       this.index = i;
       this.value = v;
    }

    @Override
    public String toString(){
        return "Index: "+index+" Value: "+value;
    }

    @Override
    public int compareTo(MyClass m) {
        return value - m.value;
    }
}

---

public static void main(String[] args){   
    MyClass[] array = new MyClass[20];

    for(int i = 0; i < array.length; i++){
       array[i] = new MyClass(i, someRandomValue); // Here I used (i*3 + 2)%5
    }
    System.out.println(Arrays.toString(array));
    Arrays.sort(array);
    MyClass [] arraySorted = Arrays.copyOfRange(array, 0, 10); //take the first ten elements
    System.out.println(Arrays.toString(arraySorted));
}

---

注意：

如果您想按索引排序具有相同值的对象，可以像这样修改比较器：

@Override
public int compareTo(MyClass m) {
    int compareValue = value - m.value;
    if(compareValue == 0)
        return index - m.index;
    return compareValue;
}

---

输出结果（使用第二个compareTo方法）：

Before :
[Index: 0 Value: 2, Index: 1 Value: 0, Index: 2 Value: 3, Index: 3 Value: 1, Index: 4 Value: 4, Index: 5 Value: 2, Index: 6 Value: 0, Index: 7 Value: 3, Index: 8 Value: 1, Index: 9 Value: 4, Index: 10 Value: 2, Index: 11 Value: 0, Index: 12 Value: 3, Index: 13 Value: 1, Index: 14 Value: 4]

After :
[Index: 1 Value: 0, Index: 6 Value: 0, Index: 11 Value: 0, Index: 3 Value: 1, Index: 8 Value: 1, Index: 13 Value: 1, Index: 0 Value: 2, Index: 5 Value: 2, Index: 10 Value: 2, Index: 2 Value: 3]

- Alexis C.

---

能否将它更改为Double值？我尝试过多次更改，但都以某些错误告终。 - Petr Šrámek

@PetrŠrámek 当然可以，只需将值字段更改为原始的 double 并在类 Double 中使用静态方法 compare，即在 compareTo 方法中使用 int compareValue = Double.compare(value, m.value);。 - Alexis C.

谢谢...在我添加这个评论之前，我尝试过了，但可能是因为我犯了一些错误，现在它运行良好。 - Petr Šrámek

@PetrŠrámek 不用谢。很酷，现在可以工作了 =) - Alexis C.

Answer 2

与其仅排序裸值，不如按照值对 (value, index) 进行排序。然后只需取前 10 个对，您便有了 10 个初始索引。

例如，您想要排序:

6 2 7 4

制作 (value, index) 对：

(6, 0) (2, 1) (7, 2) (4, 3) 

按照 value 进行排序：

(2, 1) (4, 3) (6, 0) (7, 2) 

索引：

1 3 0 2

您使用 TreeMap 的方法是正确的。您需要做的唯一修改如下所示：

class Pair implements Comparable<Pair> {
    int value;
    int index;

    @Override
    int compareTo(Pair other) { return value - other.value };
}

Map<Pair, String> map = new TreeMap<Pair, String>();

- Adam Stelmaszczyk

Answer 3

创建一个简单的类来保存两个整数，或者使用泛型来保存任何值：

class Item<T> { 
    public int index;
    public T value;
    public Item(int index, T value) {
        this.index = index;
        this.value = value;
    }
}

使用Collections.sort方法。

double[] original = { 1.0, 7.0, 3.0, -1.0, 5.0 };

List<Item> l = new ArrayList<Item<Double>>();
for (int i = 0; i < original.length; i++)
    l.add(new Item<Double>(i, original[i]));

Collections.sort(l, new Comparator<Item<Double>>() {
    public int compare(Item o1, Item o2) {
        return Double.compare(o1.value, o2.value);
    }
});

for (int i = 0; i < 10 && i < l.size(); i++) {
    System.out.printf("index: %f, value: %f%n", 
              l.get(i).index, l.get(i).value);
}

输出：

index: 3, value: -1
index: 0, value: 1
index: 2, value: 3
index: 4, value: 5
index: 1, value: 7

- azz

---

可以将它更改为Double值吗？我尝试过几次更改，但都出现了一些错误。 - Petr Šrámek

@PetrŠrámek 是的，请查看答案的修改 - azz

Answer 4

你可以通过稍微修改快速排序算法来实现这个功能，当对数组进行排序时，同时交换索引数组，就可以达到目的了。

public class Quicksort 
{
    private int[] numbers;
    private int number;

    public void sort(int[] values) {
        if (values ==null || values.length==0){
           return;
        }
        this.numbers = values;
        number = values.length;
        quicksort(0, number - 1);
    }

    private void quicksort(int low, int high) {
        int i = low, j = high;
        int pivot = numbers[low + (high-low)/2];

        while (i <= j) {
            while (numbers[i] < pivot) {
                i++;
            }
            while (numbers[j] > pivot) {
               j--;
            }

            if (i <= j) {
                exchange(i, j);
                i++;
                j--;
            }
        }

        if (low < j)
            quicksort(low, j);
        if (i < high)
            quicksort(i, high);
    }

这是我们进行更改的地方

    private void exchange(int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;

    // NOTICE THIS exchange the indexes as well
    temp = index_numbers[i];
    index_numbers[i] = index_numbers[j];
    index_numbers[j] = temp;
    }
}

- Ankit Rustagi

---

有一些注释来澄清逻辑，这将使阅读变得容易。 - iShaalan

Answer 5

简短的解决方案：

1. 创建索引数组（使用简单的for循环进行初始化）。

2. 使用自定义比较函数对该索引数组进行排序，该函数将比较其他数组中索引的值。注意：如果要按顺序打印索引，请使用稳定的排序。

3. 迭代排序后的索引数组，打印索引并计算不同值的数量（当值改变时增加计数器），当计数器变为11时停止。

- hyde