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 排序的效率待商量,场景对效率要求很高
2 年多之前 回复
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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Standard IO-----数的划分问题(三)(CCF 1187)
数的划分问题(三) 题目描述 把正整数N分解成M个正整数的和,M个加数相同但顺序不同认为是相同的方案,要求总方案数。如3=1+2跟3=2+1是两个相同的方案。 输入 第一行输入两个整数N,M(1<=M<=N<=50)。 输出 输出一个整数表示方案数。 样例输入 5 3 样例输出 2 数据范围限制 1<=M<=N<=50
两个数组元素相同,顺序不同,进行正确匹配
面试宝典中87页中面试例三,不再叙述原题。大意即是有两个数组a和b,两个数组的元素相同,但是顺序不同,写一个算法求出数组a和数组b中元素之间的对应关系。题意要求不能对同一个数组中的两个元素进行比较,也不能去取数组元素中的特定值进行比较。只能进行a和b元素之间的比较。 利用双重循环的时间复杂度为O(n^2),根据书中提示的优化方法定义一下数据结构 typedef struct { in
数的划分问题二
186 数的划分问题二 (Standard IO) 时间限制: 1000 ms 空间限制: 262144 KB 具体限制 题目描述 把正整数N分解成M个非负整数的和,即使M个数相同但顺序不同也认为是不同的方案,要求总方案数。如3=1+2跟3=2+1是两个不同的方案。 输入 第一行输入两个整数(1<=M<=N<=30)。 输出 输出一个整数表示方案数。 样例输入2 3样例输出6数
两个数组元素(相加、相乘)相关的问题
1.两个数组两个元素之和的最小K个值: 要求复杂度低于O(n^2). 已知A B两个数组,元素有序,构造新的集合S={x+y | x属于A, y属于B} 求S中最小的k个元素,最优解法。 2.两个数组(正数)两个元素之积的最小K个值:  已知A B两个数组,元素有序,构造新的集合S={x*y | x属于A, y属于B} 求S中最小的k个元素,最优解法。
数的划分问题三
题目描述 把正整数N分解成M个正整数的和,M个加数相同但顺序不同认为是相同的方案,要求总方案数。如3=1+2跟3=2+1是两个相同的方案。 输入 第一行输入两个整数N,M(1<=M<=N<=50)。 输出 输出一个整数表示方案数。 样例输入5 3样例输出2数据范围限制 1<=M<=N<=50状态: Accepted#include<cstdio> int a[2000]={0}; in
将数组元素顺序颠倒
有数组a[n],用java代码将数组元素顺序颠倒 实现代码: import java.util.Arrays; public class Test{ public static void main(String[] args) { int [] a = new int[]{ (int)(Math.random() * 1000), (int)(Math.rand
输出数组元素
#include&amp;lt;stdio.h&amp;gt;int main(){ int n,i,a[20],b[20],j; scanf(&quot;%d&quot;,&amp;amp;n); for(i=0;i&amp;lt;n;i++) { scanf(&quot;%d&quot;,&amp;amp;a[i]); } for(i=0;i&amp;lt;n;i++) { b[i]=a[i+1]-a[i]; } for(i=0;i&amp;lt;n-1;i++) { if(i%3...
比较两个数组元素是否相同,顺序可以不同,维数必须一样
// 比较两个数组元素是否相同,顺序可以不同,维数必须一样 private static boolean isSeameArr(Object[] arrA, Object[] arrB) { if (arrA == null || arrB == null) return false; if (arrA.length != arrB.length) return
2个数组中遍历相同元素或不同元素
2个数组中,遍历出不同的元素:public <T> List<T> compareList(List<T> t1, List<T> t2) { List<T> listMax; List<T> listMin; if (t1.size() > t2.size()) { listMax = t1; list
1.判断两个数组是不是有相同的元素。
#include int main(void) { int a[] = { 1, 2, 3, 4, 5, 6 }; int b[] = { 5, 6, 7, 8, 9, 6 }; int i,flag=0;                       //flag 用于监视找到相同元素并输出这一步执行没有 for (i =0; i { if (a[i] == b[i]) {