我正在用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
最佳答案
基数排序 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
关于java - 对NX3矩阵进行排序(最有效的方法),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43787367/