Câu hỏi Cách chỉ mục in của 10 giá trị nhỏ nhất trong mảng


Tôi cần chọn 10 số nhỏ nhất từ ​​mảng (với 2 000 mục) và in chỉ mục của chúng.

Lúc đầu, tôi đã cố gắng chỉ sắp xếp mảng này và các mảng giá trị in [0 đến 9]. Đó là những con số nhỏ nhất nhưng tôi đã mất các chỉ mục của các giá trị này, mà chúng có mảng không được sắp xếp.

Lựa chọn thứ hai đã được thử sử dụng treeMap mà hoạt động tốt, nhưng khi tôi có hai phím bằng nhau nó chỉ in một trong số chúng, nhưng tôi cần in cả hai.

Ví dụ về mã sử dụng với 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);  

Cho đến bây giờ tôi không sử dụng treeMap, do đó, có thể, mà tồn tại một số cách dễ dàng như thế nào sửa chữa nó. Hoặc tốt hơn là sử dụng cái gì khác?

Tôi sẽ biết ơn vì sự giúp đỡ


8
2017-11-02 14:48


gốc


Là câu hỏi "in 10 chỉ mục có giá trị nhỏ nhất" (có thể một số chỉ mục có cùng giá trị chưa được in) hoặc "chỉ mục in 10 giá trị nhỏ nhất" (có thể lớn hơn 10, thậm chí toàn bộ mảng nếu nó chỉ có 10 giá trị khác nhau hoặc ít hơn) ? - hyde
Đung. Cảm ơn bạn đã đặt tên cho chủ đề tốt hơn :) - Petr Šrámek


Các câu trả lời:


Đó là những con số nhỏ nhất nhưng tôi đã mất chỉ mục của các giá trị này,   họ có mảng không được sắp xếp

Vậy tại sao bạn không chỉ tạo một lớp để giữ các chỉ mục này? Sau đó, chỉ sắp xếp mảng của bạn theo giá trị và bạn sẽ nhận được chỉ mục được liên kết.

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));
}


Chú thích :

Nếu bạn muốn sắp xếp các đối tượng có cùng giá trị theo chỉ mục, bạn có thể sửa đổi trình so sánh của bạn như sau:

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


Đầu ra (với giây compareTo phương pháp) :

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]

4
2017-11-02 14:51



Có thể thay đổi nó cho các giá trị Double không? Tất cả các nỗ lực của tôi để thay đổi nó đã kết thúc với một số lỗi. - Petr Šrámek
@ PetrŠrámek Có, chỉ cần thay đổi trường giá trị thành nguyên thủy double và sử dụng phương pháp tĩnh compare trong lớp Double I E int compareValue = Double.compare(value, m.value); bên trong compareTo phương pháp. - Alexis C.
Cảm ơn ... Tôi đã thử nó trước khi tôi thêm bình luận này, nhưng tôi có thể có một nơi nào đó sai lầm, bởi vì bây giờ nó hoạt động tốt. - Petr Šrámek
@ PetrŠrámek Bạn được chào đón. Cool hoạt động ngay bây giờ =) - Alexis C.


Thay vì phân loại các giá trị trần, sắp xếp (value, index) cặp, liên quan đến value. Sau đó, bạn chỉ cần lấy 10 cặp đầu tiên và bạn có 10 chỉ số gốc.

Ví dụ: bạn muốn sắp xếp:

6 2 7 4

Chế tạo (value, index) cặp:

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

Sắp xếp theo value:

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

Chỉ số:

1 3 0 2

Cách tiếp cận của bạn với TreeMap Ổn. Sửa đổi duy nhất bạn phải làm như sau:

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>();

2
2017-11-02 14:53





Tạo một lớp đơn giản để giữ hai int, hoặc sử dụng Generics cho bất kỳ giá trị nào:

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

Và tận dụng 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);
}

Đầu ra:

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

1
2017-11-02 15:06



Có thể thay đổi nó cho các giá trị Double không? Tất cả các nỗ lực của tôi để thay đổi nó đã kết thúc với một số lỗi. - Petr Šrámek
@ PetrŠrámek Có, hãy xem các sửa đổi đối với câu trả lời - azz
Cảm ơn bạn rất nhiều, bây giờ nó hoạt động tốt - Petr Šrámek


Bạn có thể thực hiện việc này với Sắp xếp nhanh được sửa đổi một chút, trong khi sắp xếp mảng nếu bạn trao đổi mảng chỉ mục, nó sẽ thực hiện thủ thuật

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);
    }

Đây là nơi chúng tôi thực hiện thay đổi

    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;
    }
}

0
2017-11-02 14:57



Nó sẽ dễ đọc với một số ghi chú làm rõ logic - iShaalan


giải pháp ngắn:

  1. Tạo mảng các chỉ mục (đơn giản cho vòng lặp để khởi tạo).

  2. Sắp xếp mảng chỉ mục đó với hàm so sánh tùy chỉnh, so sánh các giá trị cho chỉ mục trong mảng khác. Lưu ý: sử dụng một loại ổn định, nếu bạn muốn in chỉ mục theo thứ tự.

  3. Lặp lại mảng chỉ mục đã sắp xếp, chỉ mục in và đếm các giá trị riêng biệt (tăng bộ đếm khi thay đổi giá trị), dừng khi bộ đếm trở thành 11.


0
2017-11-02 15:04