2 kdrj042 kdrj042 于 2016.03.18 22:54 提问

2个数组元素顺序不同,认为是同一个数组

有2个数组比如[1,2,3,4]和[4,3,2,1],仅仅排序不同,有什么快速的算法认为是同一个数组?
或者数组元素能算出key,而此key和元素顺序无关。
求Java实现

4个回答

devmiao
devmiao   Ds   Rxr 2016.03.18 22:57

对它排序,然后比较,或者对数组求和,得到hash,如果和相同虽然不一定数组相同,但是和不同,一定不同,所以可以进一步筛选。

kdrj042
kdrj042 排序的效率待商量,场景对效率要求很高
一年多之前 回复
bealing
bealing   Rxr 2016.03.18 23:31

如果数组没有重复,放到set中,然后直接比较set,就OK了

wojiushiwo945you
wojiushiwo945you   Ds   Rxr 2016.03.19 08:43

要判断两个数组相同,而且还要考虑的数组元素是无序,最简单的还是先排序,再调用数组工具类Arrays的equals比较。
如果你的场景对效率要求高,排序效率还取决于你的数组数据量,如果像你题给的短数组的话,排序不存在效率问题的。
参考代码:

 public static void main(String[] args) {
    int [] a = {1,2,4,3};
    int [] b = {2,1,3,4};
    //先对数组排序
    Arrays.sort(a);
    Arrays.sort(b);
    //再调用数组工具类的equals,这个方按元素顺序比较的
    boolean isEqual = Arrays.equals(a,b);
    System.out.println(isEqual);
}
leilba
leilba   Rxr 2016.03.19 10:11

如果对空间没有限制的话,可以给你一个时间复杂度为 O(n)的方法:
1.比较两个数组的长度,如果不等的话显然可以排除掉
2.长度相等的情况下,用一个大数组来记录其中一个数组的每个值的对应的个数,同时让另一个数组的值的个数来减
3.最后统计大数组对应的位置是否全为0,是的话说明这两个数组是相等的,否则不等。

需要注意的是,这个数组值的范围为-MAX_SIZE/2 ~ MAX_SIZE/2 之间

 public class Main {
    //数值的范围是从 -100005/2 ~ 100005/2
    static final int MAX_SIZE = 100005;
    static final int HALF_MAX_SIZE = MAX_SIZE/2;

    public static void main(String args[]) {
        int  map[]=new int[MAX_SIZE];

        int array1[] = {
            1,2,3,4
        };
        int array2[] = {
            4,3,2,1
        };

        boolean isEqual  = true;

        //比较长度,不等的话直接排除
        if(array1.length == array2.length) {
            //进行值的数量削减
            for(int i=0;i<array1.length;i++) {
                map[array1[i]+HALF_MAX_SIZE]++;
                map[array2[i]+HALF_MAX_SIZE]--;
            }

            //统计数量是否全部抵消掉
            for(int i=0;i<array1.length;i++) {
                if(map[array1[i]+HALF_MAX_SIZE]!=0){
                    isEqual = false;
                    break;
                }
            }
        }else {
            isEqual = false;
        }

        if(isEqual) {
            System.out.println("is Equal");
        }
        else {
            System.out.println("is not Equal");

        }

    }
}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!