java - 对NX3矩阵进行排序(最有效的方法)

Question

我正在用JAVA编写Mo算法的更新代码，所以在这里我们必须以这种方式对N X 3矩阵的ArrayList进行升序排序

ArrayList 的形式为

Ai,Bi,Ci

例如:

1,2,3
2,3,4
1,2,1
2,3,5

所以要排序，首先查找所有的Ai，如果有冲突，如Ai中的1,2,3和1,2,1，则查找Bi，如果有冲突，则查找Bi Ci，并相应地对它们进行排序。

Sorted array
1,2,1
1,2,3
2,3,4
2,3,5

那么有没有什么数据结构可以对它们进行排序，而无需编写一大段代码？

那些在评论中索要我代码的人-->

// RIGHT NOW I HAVEN'T MADE AN N X # MATRIX ,WHAT I HAVE DONE IS TAKEN 3 ARRAYLISTS , yes I WILL CHANGE IT INTO A SINGLE ARRAYLIST OF SIZE N X 3
public class MoSAlgorithmUpdates {

public static void main(String[] args) throws IOException {
    //finding no of distict numbers
    BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
    String str;
    //Taking the Array Now
    str=br.readLine();
    ArrayList<Integer> arr=new ArrayList<Integer>();
    StringTokenizer st = new StringTokenizer(str," ");
    while(st.hasMoreTokens())
    {
        arr.add(Integer.parseInt(st.nextToken()));
    }

    // Total q queries including updates + finding distinct numbers

    int Q;
    str = br.readLine();
    Q = Integer.parseInt(str);
    int[] q1=new int[Q];
    int[] q2=new int[Q];
    int[] q3=new int[Q];
    int[] q4=new int[Q];
    ArrayList<Integer> query1=new ArrayList<Integer>();// RIGHT NOW I HAVEN'T MADE AN N X # MATRIX ,WHAT I HAVE DONE IS TAKEN 3 ARRAYLISTS , yes I WILL CHANGE IT INTO A SINGLE ARRAYLIST OF SIZE N X 3
    ArrayList<Integer> query2=new ArrayList<Integer>();// RIGHT NOW I HAVEN'T MADE AN N X # MATRIX ,WHAT I HAVE DONE IS TAKEN 3 ARRAYLISTS , yes I WILL CHANGE IT INTO A SINGLE ARRAYLIST OF SIZE N X 3
    ArrayList<Integer> query3=new ArrayList<Integer>();// RIGHT NOW I HAVEN'T MADE AN N X # MATRIX ,WHAT I HAVE DONE IS TAKEN 3 ARRAYLISTS , yes I WILL CHANGE IT INTO A SINGLE ARRAYLIST OF SIZE N X 3
    ArrayList<Integer> update1=new ArrayList<Integer>();
    ArrayList<Integer> update2=new ArrayList<Integer>();
    ArrayList<Integer> update3=new ArrayList<Integer>();
    //int[] update1=new int[Q];
    int noofupdates=0;
    //noofupdates=time

    for(int i2=0;i2<Q;i2++)
    {
        str=br.readLine();
        StringTokenizer st2 = new StringTokenizer(str," ");

        q1[i2]=Integer.parseInt(st2.nextToken());

        q2[i2]=Integer.parseInt(st2.nextToken());
        q3[i2]=Integer.parseInt(st2.nextToken());

        if(q1[i2]==1)
        {
            query1.add(q2[i2]);
            query2.add(q3[i2]);
            query3.add(noofupdates);
        }
        else
        {
            update1.add(q2[i2]);
            update2.add(q3[i2]);
            noofupdates++;
        }
    }
  }
}

最后一个查询-->

在 Mo 的算法更新中，我们通过以下方式排列 ArrayList

int sqrt = Math.sqrt(N) // N is the length of ArrayList containing all the 
                        // numbers from which range queries have to be told 

现在对 .数字为

现在让我们说 L，R，时间例如

1,3,3
2,3,4
2,1,1
2,3,5

因此按 L、R、时间对它们进行排序返回结果为

Sorted array
1,3,3
2,1,1
2,3,4
2,3,5

现在必须对它们进行排序，如何做到这一点？最终输出必须类似于没有平方根的值，即值 L，R，时间不应改变，但必须使用 进行排序。如何实现这一目标——？

最终输出可能如下所示，具体取决于 N 的值

2,1,1
1,3,3 //Very Imp see this it is sorted
2,3,4
2,3,5

Answer 1

基数排序 https://en.wikipedia.org/wiki/Radix_sort

您可以使用集合的默认排序方法

Collections.sort(yourArrayN2, comparator);

您应该定义比较器，从第一个元素开始比较两个数组(我们假设这些数组/列表具有相同的大小；否则您将修改比较器)。

比较器:

    public class ListComparator implements Comparator<List<Integer>> {

        @Override
        public int compare(List<Integer> list1, List<Integer> list2) {
            if (list1 == null || list2 == null || list1 == list2) {
                throw new IllegalArgumentException();
            }

            int size = list1.size();
            if (size != list2.size()) {
                throw new IllegalArgumentException();
            }

            for (int i = 0; i < size; i++) {
                int delta = list1.get(i) - list2.get(i);
                if (delta != 0) {
                    return delta;
                }
            }

            return 0;
        }
    }

及其用法

public class App {

    public void execute() {
        List<List<Integer>> list2D = make2DList();
        printList2D(list2D);
        System.out.println("\n");
        Collections.sort(list2D, new ListComparator());
        printList2D(list2D);
    }

    //This is where you create your 2D list. It can be read from file, etc.
    private List<List<Integer>> make2DList() {
        List<List<Integer>> res = new ArrayList<>(3);
        res.add(makeList(1,2,3));
        res.add(makeList(2,3,4));
        res.add(makeList(1,2,1));
        res.add(makeList(2,3,5));
        return res;
    }

    private List<Integer> makeList(Integer ... numbers) {
        List<Integer> res = new ArrayList<>();
        for (Integer i : numbers) {
            res.add(i);
        }
        return res;
    }

    private void printList2D(List<List<Integer>> list2D) {
        for (List<Integer> list : list2D) {
            printList(list);
        }
    }

    private void printList(List<Integer> list) {
        int size = list.size();
        int lastIndex = size - 1;
        for (int i = 0; i < lastIndex; i++) {
            System.out.print(list.get(i) + ", ");
        }
        System.out.print(list.get(lastIndex) + "\n");
    }
}

打印

1, 2, 3
2, 3, 4
1, 2, 1
2, 3, 5


1, 2, 1
1, 2, 3
2, 3, 4
2, 3, 5