算法数组--力扣2007题

1.题目描述

一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。

给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。

2.个人理解

该题是要判断双倍数组的元素组，1.该双倍数组的长度一定是偶数，2.且原数组的元素大部分是小于，成了倍数的元素。3.对于原素组的元素必有 nums[i]*2 == 双倍数组中的其中一个元素

3.解题思路

1.判断数组的程度是否是偶数

2.对元素进行排序

3.创建一个新的数组其长度为二倍数组的一半，创建一个ArrayList存放没有匹配成功的二倍数组中的元素，把匹配成功的二倍数组的元素删除，并存放在新数组中。最后若ArrayList为null则说明全部匹配，否则该二倍数组没有原数组。

代码如下：

  public static int[] findOriginalArray(int[] changed) {
            if (changed.length % 2 != 0){
                return new int[]{};
            }
            Arrays.sort(changed);
            int[] arr = new int[changed.length/2];

           ArrayList<Integer> list = new ArrayList<>();
            int count=0;
           for (int i=0;i<changed.length;i++){
               if (!list.isEmpty() && list.get(0) * 2 == changed[i]){
                   arr[count] = list.remove(0);
                   count++;

               }
               else {
                   list.add(changed[i]);
                   System.out.println(list);
               }
           }
           if (list.isEmpty()){
               System.out.println(arr.length);
               return arr;
           }
        return new int[]{};
    }

 该思路用arrayList模拟队列，做的。效率太低，一定不是最好的方法。仅供参考。