百万级的数据量的数组求出现次数最多的子数组！！！

Question

例如有这样一个数组  int[][] array = {{105,78},{111,135},{124,11},{124,11},{124,11},{105,78}};
要求取出，出现次数最多的子数组和出现的次数。可能同时存在有两个或N个数组都出现相同次数的可能。（数组可能是百万级的数据量。要求时间复杂度最小。）

Answer 1

这个题时间复杂度和空间复杂度最小的算法是位排序。时间复杂度是2n，即两遍扫描即可求出答案。举个简单的例子，对0到9之间的不重复任意九个数排序，我们先设置一个数组（比如a[]），数组初始化为0，依次扫描这九个数，读到几就放到数组下标为几的位置，比如读到4，就放在a[4]。一遍扫描完了之后，也就排好序了。对lz所提的问题，由于数据量比较大，需要按位排序。即：申请一个int型的空间，它有32个位，则我们可以对范围在32之内的数进行排序。如果数据量有一千万那么大，那么我们需要一个10,000,000/32这么大的整型数组。这个数组（应该说是位数组）初始化为0，如果一个数出现过一次，就将数组的相应的位置为1。另外设置一个二维数组，如果一个数出现过两次以上，则将该数和他的出现次数保存在二维数组中。当把这一千万个数字扫描完了以后，所以出现两次以上的数和它的出现次数已经保存在二维数组中。只有在扫描一次二维数组，就能找到出现次数最多的数。如果二维数组为空，则所有的数都只出现了一次。我以前做个一个类似的题，数据量是一千万，要求占用的内存空间不能超过1.5M，时间不能超过1s，用的就是这个算法。

Answer 2

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Random;/**
 * http://topic.csdn.net/u/20081226/16/68ba2e25-7cb9-47c5-86a7-0e9438f4dcd8.html?seed=1589208714
 * 百万级的数据量的数组求出现次数最多的子数组！！！ 
 * 例如有这样一个数组  int[][] array = {{105,78},{111,135},{124,11},{124,11},{124,11},{105,78}}; 
 *  要求取出，出现次数最多的子数组和出现的次数。
 *  可能同时存在有两个或N个数组都出现相同次数的可能。（数组可能是百万级的数据量。要求时间复杂度最小。）
 * @author
 *
 */
public class TestArray {
static final Random random=new Random();
private static int[][] createArray(int len,int range){
int[][] arr=new int[len][];
for (int i=0;i<len;i++){
arr[i]=new int[2];
arr[i][0]=random.nextInt(range);
arr[i][1]=random.nextInt(range);

}
return arr;
}
/**
 * @param args
 */
public static void main(String[] args) {
int[][] t=createArray(1000000,1000);
//int[][] t= {{105,78},{111,135},{124,11},{124,11},{124,11},{105,78}};
Arrays.sort(t, new Comparator(){
public int compare(Object o1, Object o2) {
int[] a1=(int[])o1;
int[] a2=(int[])o2;
return (a1[0]==a2[0])?(a1[1]-a2[1]):(a1[0]-a2[-0]);
}});
int[] mem=t[0];
int count=1;
int max=0;
List<int[]> result=new ArrayList<int[]>();
for (int i=1;i<t.length;i++){
int[] temp=t[i];
if (temp[0]==mem[0]&&temp[1]==mem[1]){
count++;
} else {
if (count>max){
max=count;
result.clear();
result.add(mem);
} else if (count==max){
result.add(mem);
}
mem=temp;
count=1;
}
}
if (count>max){
max=count;
result.clear();
result.add(mem);
} else if (count==max){
result.add(mem);
}
System.out.println(max);
for (int i=0;i<result.size();i++){
System.out.println(result.get(i)[0]+"\t"+result.get(i)[1]);
}
}}

Answer 3

大概的看了一下9楼的程序，是先利用Array的sort()方法对数组进行了一个排序，然后依次扫描数组查找出现次数最多的子数组。
我不知道Array的sort()方法采用了什么排序算法，但是肯定不是位排序，也就是说时间复杂性肯定比n大。
jdk封装了很多的底层实现，但不总是最好的。有的时候不能总是依赖jdk的内部实现。lz的题应该是一道算法题，这个就不适合用Array的sort()方法来排序。ps:测试了一下9楼的程序，一百万数据的时候速度还是可以接受的~~
ps ag:lz写程序总是不写注释么？

Answer 4

对lz所提的问题，由于数据量比较大，需要按位排序。即：申请一个int型的空间，它有32个位，则我们可以对范围在32之内的数进行排序。如果数据量有一千万那么大，那么我们需要一个10,000,000/32这么大的整型数组。这个数组（应该说是位数组）初始化为0，如果一个数出现过一次，就将数组的相应的位置为1。另外设置一个二维数组，如果一个数出现过两次以上，则将该数和他的出现次数保存在二维数组中。当把这一千万个数字扫描完了以后，所以出现两次以上的数和它的出现次数已经保存在二维数组中。只有在扫描一次二维数组，就能找到出现次数最多的数。如果二维数组为空，则所有的数都只出现了一次。 

Answer 5

这种情况不适合用你说的方法。因为不知道[n1,n2]的最大值。假设[1000000,1000000]，你预产生的数组就得1百万X1百万，天文数字了！
如果题目给定了n1/n2的最大值就是100，那么产生一个100X100的数组是可以接受的。Arrays.sort()是用的快速排序，时间复杂度是O(n*lgn)
加上后面的查找最大，总时间复杂度是O(n*lgn+n)，也就是O(n*lgn)。应该算快的了。

Answer 6

果然是快排~~ls说的对，如果n1、n2上限很大的话确实会造成初始数组过大的问题。不过lz的问题数据量只在千万以内，所以理论上如果能找到一个好的哈希算法，可以将可能出现的所有数值散列在一个千万位的数组内。如果n1n2确实无上限无规则的话，确实实现不了~~就看lz能不能找到这么一个哈希算法了。不过貌似lz不打算来结这个贴了~~ps:十二楼是干嘛的？原话复制一遍粘贴过来，你的小4000分不都是这么来的吧O(∩_∩)O~