Лексикографически отсортировать массив точек

Question

Я пытаюсь найти массив NX2 всех целых чисел в лексикографическом порядке. Я не понимаю, как этого добиться. Кроме того, это должно быть сделано как можно меньше времени. Вот пример.

Введите

2 2
1 1
4 3
2 1
10 1

выход

1 1
2 1
2 2
4 3
10 1

Answer 1

1. Реализация собственного класса Point с двумя полями целых чисел.
2. Заставить его реализовать Comparable (или реализовать Comparator для этого класса).
3. Заполните массив или Перечислите этих точек и отсортируйте его, используя соответствующую сортировку: Arrays.sort () или Collections.sort () соответственно.
4. Выполните итерацию полученного массива / списка и извлеките обратно ваши точки.

Answer 2

Это в основном та же проблема, что и сортировка группы целых чисел, за исключением того, что вместо целых чисел у вас есть набор объектов (в данном случае кортежи - или в вашем коде два массива int), которые необходимо отсортировать.

В отличие от Python, Java не выводит автоматически лексикографический порядок таких вещей, как int [], поэтому вы можете просто передать его в функцию сортировки и ожидать, что он будет работать. К счастью, java позволяет вам определить, каким должен быть порядок, а затем использовать встроенный метод сортировки для его сортировки. Это делается путем реализации Comparator и последующего определения его compare метода, который говорит ему, как сравнивать два объекта.

(очень упрощенный) пример, приведенный ниже.

import java.util.*;

class Main{
        public static void main(String args[]){
                int[][] array={{2,2},{1,1},{4,3},{2,1},{10,1}};
                Arrays.sort(array, new Comparator<int[]>(){
                        public int compare(int[] a, int[] b){
                                //assumes array length is 2
                                int x,y;
                                if (a[0]!=b[0]) {
                                        x=a[0];y=b[0];
                                }
                                else{
                                        x=a[1];y=b[1];
                                }
                                if (x<y) return -1;
                                else if (x==y) return 0;
                                else return +1;
                        }
                });
                for(int[] term: array){
                        System.out.println(Arrays.toString(term));
                }
        }
}

Answer 3

Здесь попробуйте использовать этот класс Point с компаратором:

class MyPoint implements Comparable <MyPoint> {
    int x, y;
    public MyPoint(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int compareTo(MyPoint pt) {
        int cmp = Integer.compare(x, pt.x);
        if (cmp == 0) {
            return Integer.compare(y, pt.y);
        } else {
            return cmp;
        }
    }

}

После всего, что вам нужно сделать, это создать несколько объектов Point и отсортировать их. Вот пример:

    ArrayList<MyPoint> pts = new ArrayList<MyPoint>(4);
    pts.add( new MyPoint(3, 5));
    pts.add( new MyPoint(2, 3));
    pts.add( new MyPoint(3, 4));
    pts.add( new MyPoint(1, 5));
    Collections.sort(pts);
    for (int i = 0; i < pts.size(); i++) {
        MyPoint pt = pts.get(i);
        System.out.println(pt.x + " " + pt.y);
    }   

Выход:

1 5
2 3
3 4
3 5

Answer 4

@ amit объяснил что делать. Я просто хотел добавить, что вы не хотите сортировать числовые данные лексикографически. Если вы сделаете это, вы получите

1 1
10 1
2 1
etc.

Потому что лексикографически 10 - это только после 1 и до 2. Вы хотите выполнить обычную числовую сортировку. Иногда это называется «натуральный» сорт.