两个数组如何高速合并？

Question

我有两个数组
         int[][] a={{2,3},{11,2},{7,4},{9,3}};
     int[][] b={{3,4},{9,1},{2,2},{6,3},{11,1}};
要求a和b数组合并   结果变为
int[][] c={{2,5},{3,4},{6,3},{7,4},{9,4},{11,3}};
不能用两个for嵌套  意思就是性能要比两个for嵌套要高

Answer 1

不用for用while吗  额……

Answer 2

不是不能用for  意思是不能嵌套  嵌套的话就是n*m了 我希望是n+m。。

Answer 3

既然你都提到性能了，那么为什么要使用数组存储这些数据呢。
当初就该采用哈希表形式的数据结构，比如HashMap 

Answer 4

要是只是实现，用个map更好看点。用数组的话，假如你的第一个数是不重复的，而且最大的数不是很大，1：遍历a[i][j] ,c[a[i][0]]+=a[i][1]
2：遍历b[i][j] ,c[b[i][0]]+=b[i][1]
3：再遍历c  生成2维数据。

Answer 5

map我大致看了一下实现  get方法和contain方法之类的还是for嵌套的  而且不是都说数组是性能最好的么

Answer 6

    int[][] a={{2,3},{11,2},{7,4},{9,3}};
    int[][] b={{3,4},{9,1},{2,2},{6,3},{11,1}};
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int[] x : a) {
      map.put(x[0], x[1]);
    }
    for (int[] x : b) {
      Integer y = map.get(x[0]);
      if (y != null) {
        map.put(x[0], y+x[1]);
      } else {
        map.put(x[0], x[1]);
      }
    }
    int[][] result = new int[map.size()][2];
    Set<Integer> keys = map.keySet(); 
    // Integer可能不需要，不过稳妥一点，还是直接，保证顺序
    // Set<Integer> keys = new TreeSet<Integer>(map.keySet());
    int count = 0;
    for (Integer key:keys) {
      result[count][0] = key;
      result[count++][1] = map.get(key);
    }

Answer 7

这个是相对的 
汇编效率不是更好吗，那你为什么不用？java的数组是一个对象 跟C语言不一样
java建议使用集合，而非数组

Answer 8

如果，a[i][0]和b[i][0]的范围已知，而且a[i][1]和b[i][1]都是正数的话，可以更简化
    int[][] a={{2,3},{11,2},{7,4},{9,3}};
    int[][] b={{3,4},{9,1},{2,2},{6,3},{11,1}};
    int[] c = new int[20/*key的范围，可能考虑负数什么*/];
    for (int[] x:a) {
      c[x[0]] += x[1];
    }
    for (int[] x:b) {
      c[x[0]] += x[1];
    }
    int count = 0;
    int[][] temp = new int[c.length][2];
    for (int i = 0; i < c.length; i++) {
      if (c[i] > 0) {
        temp[count][0] = i;
        temp[count++][1] = c[i];
      }
    }
    int[][] result = new int[count][2];
    System.arraycopy(temp, 0, result, 0, count);

Answer 9

也就是说，可以用两个for循环，但不能嵌套，是么？
还能用其他java api的东西么？比如集合

Answer 10

里面的for，是hash冲突的情况下，对于integer类型的key来说，由于integer.hashCode就是其value，也就是1的hashCode = 1, 100的hashCode= 100，所以不存在冲突，hashMap的效率，就是线性的。

Answer 11

a[i][0]和b[i][0]范围是已知的 都是1~100  并且a[i][0]和b[i][0] 实话实说，其实a和b的长度都不是很长在1~6范围 

Answer 12

好像.NET有个高速合并吧！！！

Answer 13

copymemory直接复制内存块,够快了吧

Answer 14

虽然不知道LZ在说什么，但还是觉得LZ很NB

Answer 15

循环语句是所有数据算法的基础,你给我找个不带循环的算法来看看...
而且,谁教你的FOR有性能问题?
你确定不用FOR性能就一定比用FOR强?
楼上有句说的好,盲目追求性能就是完全不懂性能
有时间花在纠结用不用FOR上面,还是花点时间去翻翻数据结构的书

Answer 16

如果对空间没要求，再加一个数组做相对地址更好
int min,max;
int[]indexs=new int[a.length+b.length];
for(int i=0;i<indexs.length;i++){
indexs[i]=-1;
}
用来保存a[i][0]相对min的值，c的长度最大就变成a.length+b.length

Answer 17

改一下，负数也可以，还不知道有没有更好的~~
public static void main(String[] args) {
int[][] a = { { -2, 3 }, { 11, 2 }, { 7, 4 }, { 9, 3 } };
int[][] b = { { 3, 4 }, { 9, 1 }, { -2, 2 }, { 6, 3 }, { 11, 1 } }; // 得到最大最小值
int max = a[0][0], min = a[0][0];
for (int[] x : a) {
if (x[0] > max) {
max = x[0];
}
if (x[0] < min) {
min = x[0];
}
}
for (int[] x : b) {
if (x[0] > max) {
max = x[0];
}
if (x[0] < min) {
min = x[0];
}
} // 初始化，设置默认值
int[] c = new int[max - min + 1];
for (int i = 0; i < c.length; i++) {
c[i] = min - 1;
} // 赋值
for (int[] x : a) {
c[x[0] - min] = x[1];
}
for (int[] x : b) {
// 如果这个位置没有值
if (x[0] < min) {
c[x[0] - min] = x[1];
} else {
// 否则值相加
c[x[0] - min] += x[1];
}
} //计算key的个数
int maxcount = 0;
for (int i = 0; i < c.length; i++) {
if (c[i] >= min) {
maxcount++;
}
} //得到结果
int[][] result = new int[maxcount][2];
int count = 0;
for (int i = 0; i < c.length; i++) {
if (c[i] >= min) {
result[count][0] = i + min;
result[count++][1] = c[i];
}
} print(result);
} static void print(int[][] d) {
System.out.print("{");
for (int[] x : d) {
System.out.print("{");
System.out.print(x[0]);
System.out.print(",");
System.out.print(x[1]);
System.out.print("}");
}
System.out.print("}");
}

Answer 18

好了 该结贴了 邀请的朋友都没来  有点失落  我后来又想了一下 于是写出下面的纯面向过程的代码 没啥技术含量
public static int[][] add(int[][] target,int[][] first) {
int len1=target.length;
int len2=first.length;
Set<Integer> key=new HashSet<Integer>();
Arrays.sort(target,MySort());
Arrays.sort(first,MySort());
for(int i=0;i<len1;i++){
key.add(target[i][0]);
}
for(int i=0;i<len2;i++){
key.add(first[i][0]);
}
int[][] temp=new int[key.size()][];
Iterator<Integer> i=key.iterator();
int k=0;
int a=0;
int b=0;
int index=0;
while(i.hasNext()&&index<key.size()){
k=i.next();
if(a<len1&&k==target[a][0]&&k!=first[b][0]){
temp[index]=new int[]{target[a][0],target[a][1]};
a++;
}
if(b<len2&&k==first[b][0]&&k!=target[a][0]){
temp[index]=new int[]{first[b][0],first[b][1]};
b++;
}
else if((a<len1&&b<len2)&&k==target[a][0]){
temp[index]=new int[]{first[b][0],first[b][1]+target[a][1]};
a++;
b++;
}
index++;
}
return temp;
}
虽然14楼的写的不错  但是根据我这里的实际情况显然循环次数有点多  以上这些

Answer 19

差点忘了 我那个MySort()对二维数组进行排序   是根据key排序的  以下是自定义排序类class Sort implements Comparator<int[]>{ @Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
}

Answer 20

晕啊，楼主不会是以为Arrays.sort中木有循环吧，

Answer 21

你看清楚他们的方法吧  我的key范围可是1~100   他们的方法有个数组的容量是最大的key的值 随随便便来个几十的key 循环次数几乎都上百了   我的明显次数少多了   你加加看呗

Answer 22

     int[][] a={{2,3},{11,2},{7,4},{9,3}};
        int[][] b={{3,4},{9,1},{2,2},{6,3},{11,1}};
        
     //   int[][] c={{2,5},{3,4},{6,3},{7,4},{9,4},{11,3}};
        List<int[]> al = Arrays.asList(a);
        List<int[]> bl = Arrays.asList(b);
        HashMap<Integer, Integer> ah = new HashMap();
        HashMap<Integer, Integer> bh = new HashMap();
        for (int[] value : al) {
            ah.put(value[0], value[1]);
        }
        for (int[] value : bl) {
            bh.put(value[0], value[1]);
        }
        Set<Integer> keys = bh.keySet();
        Iterator<Integer> it= keys.iterator();
        while(it.hasNext()) {
            int i = it.next();
            if (ah.containsKey(i)) {
                ah.put(i, ah.get(i) + bh.get(i));
            } else {
                ah.put(i, bh.get(i));
            }
        }
        /*
         * print result
         */
        Set<Integer> keys1 = ah.keySet();
        Iterator<Integer> it1= keys1.iterator();
        while(it1.hasNext()) {
            int i = it1.next();
            System.out.println("key" + i + "value" + ah.get(i));
        }

Answer 23

System.arraycopy(src, srcPos, dest, destPos, length)

Answer 24

有了这个前提就好办了，建一个长度100的数组c[100]，全部置0，表示没有数据，然后分别用for循环遍历a和b，把{x,y}中的y加到c[x]上面，处理完后，用for循环扫描C，遇到不为0的c[i]就需要在结果数组d[]中添加{i,c[i]}
代码不写了

Answer 25

这样看是不是简单点，把两个数组合并成{2,3},{11,2},{7,4},{9,3},{3,4},{9,1},{2,2},{6,3},{11,1}。
然后冒泡排序法，相等就相加。把最大的拿出来给c[]。就变成{2,3},{7,4},{9,3},{3,4},{9,1},{2,2},{6,3}。
把{11,3}给c[].同样{9,4}给c[]，最后长数组空了为止。

Answer 26

针对乐高坦克和30L童鞋的代码进行的改动前提 位置0的值不为负数并且小于Integer.MAX_VALUE其实用Map的方式最简洁 可能严格来讲的确算是嵌套 避免嵌套的方式就是用这种数组了.. package example;import java.util.Arrays;public class StudyArray {
public static void main(String[] args) {
int[][] a = { { 2, 1 }, { 11, 1 }, { 7, 1 }, { 9, 1 } };
int[][] b = { { 3, 1 }, { 9, 1 }, { 2, 1 }, { 6, 1 }, { 11, 1 } };
int[][] result = merge(a, b); System.err.print("{");
for (int i = 0; i < result.length; i++) {
System.err.print("{" + result[i][0] + "," + result[i][1] + "}");
}
System.err.print("}");
} public static int[][] merge(int[][] a1, int[][] a2) {
int[][] result = null;
int[][] merge = null;
int[][] table = null;
int[][] first = null;
int[][] second = null; int resultsize = 0;
int max = 0;
int min = 0; if (a1.length > a2.length) {
first = a2;
second = a1;
} else {
first = a1;
second = a2;
}
resultsize = second.length;
merge = new int[second.length * 2][2]; for (int i = 0; i < second.length; i++) {
if (max < second[i][0]) {
max = second[i][0];
}
if (min > second[i][0]) {
max = second[i][0];
}
}
table = new int[max - min + 1][2]; Arrays.fill(table, null); for (int i = 0; i < first.length; i++) {
if (first[i][0] > max) {
merge[++resultsize] = first[i];
} else {
table[first[i][0] - min] = first[i];
}
} for (int i = 0; i < second.length; i++) {
if (table[second[i][0] - min] == null) {
table[second[i][0] - min] = second[i];
} else {
table[second[i][0] - min][1] += second[i][1];
} merge[i] = table[second[i][0]];
} result = new int[resultsize][2];
System.arraycopy(merge, 0, result, 0, resultsize);
return result;
}
}

Answer 27

你这个效率还不如14楼的高。当然按照你的要求“a[i][0]和b[i][0]范围是已知的 都是1~100 并且a[i][0]和b[i][0] 实话实说，其实a和b的长度都不是很长在1~6范围”，14楼的效率也还不如直接双循环的效率高。
分析一下14楼的循环次数：
设 A的又n个元素，B有m个元素
双循环的效率是 n*m
按14楼的代码，循环次数是 n+m+100;
现在要
n*m>n+m+100
n*m-n-m>100
n*(m-1)-m>100
n*(m-1)-m-1+1>100
n*(m-1)>101取n和m总个数最少的情况,n=11,m=11，总元素个数必须大于22个是，14楼代码的效率才会高于双循环

Answer 28

楼主和14楼的结合版，效率稍微好一点 int[][] x = { { 2, 3 }, { 11, 2 }, { 7, 4 }, { 9, 3 } };
int[][] y = { { 3, 4 }, { 9, 1 }, { 2, 2 }, { 6, 3 }, { 11, 1 } };
int[][] a;
int[][] b;
Map<Integer, Integer> c = new HashMap<Integer, Integer>();
if (x.length > y.length) {
a = x;
b = y;
} else {
a = y;
b = x;
}
for (int i = 0; i < b.length; i++) {
if (!c.containsKey(a[i][0])) {
c.put(a[i][0], a[i][1]);
} else {
int m = c.get(a[i][0]) + a[i][1];
c.remove(a[i][0]);
c.put(a[i][0], m);
} if (!c.containsKey(b[i][0])) {
c.put(b[i][0], b[i][1]);
} else {
int n = c.get(b[i][0]) + b[i][1];
c.remove(b[i][0]);
c.put(b[i][0], n);
}
} for (int i = b.length; i < a.length; i++) {
if (!c.containsKey(a[i][0])) {
c.put(a[i][0], a[i][1]);
} else {
int m = c.get(a[i][0]) + a[i][1];
c.remove(a[i][0]);
c.put(a[i][0], m);
}
} int[][] result = new int[c.size()][2];
int i = 0;
for (int key : c.keySet()) {
result[i][0] = key;
result[i][1] = c.get(key);
i++;
}

Answer 29

就像楼上有的网友说的：Java更注重以空间复杂度换取时间复杂度。
对这个算法本身来说，可能对C程序员更有意义些。但是我更想知道的是，它有什么实用价值？
希望大家能点拨一下。。

Answer 30

如果是说实现功能的话我想大部分java程序员都会首先考虑map，实现简单，逻辑清晰……
如果在大项目中纠结这些的话……
LZ不是想自己做个数值类的map实现吧

Answer 31

难道没有学过 《数据结构》吗？知道一个叫散列（hashMap）的东东吗，如果没有hash冲突，也就是绝大部分情况下，get， contain方法都是线性的。只要你把hash因子设低一点，完全可以没有hash冲突，完全线性根据内存地址读取。

Answer 32

没有学过数据结构  我们老师以前只给我们举过介绍过一些数据结构的例子  链表之类的  你的意思就是map的get在hash不冲突的情况下get可以直接取值是吧  但是别人说hash方面很耗cpu资源  不知道是不是这样子

Answer 33

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }