LeetCode-954. 二倍数对数组

题目描述：

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。

示例 1：
输入：arr = [3,1,3,6]
输出：false

示例 2：
输入：arr = [2,1,2,6]
输出：false

示例 3：
输入：arr = [4,-2,2,-4]
输出：true
解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]

提示：

0 <= arr.length <= 3 * 104
arr.length 是偶数
-105 <= arr[i] <= 105

解题思路一：

设cnt[x] 表示 arr 中 x 的个数。

unordered_map cnt;关键字key为arr里的数字，值value为arr里的数字的个数
若cnt[0]%2==1：即0的个数为奇数的话直接返回false
1、reserve
当内存受限时（此时虚拟内存都快耗尽），由于push_back由于每次发现存储空间不够时，默认会申请原来空间的两倍，此时申请空间时就会发生错误。

因此如果知道 vector需要多少内存的话，最好先用 reserve申请一下空间 ，即预申请一定的空间。

设 x 为arr 中绝对值最小的元素，由于没有绝对值比 x 更小的数，因此 x 只能与 2x 匹配。

如果此时cnt[2x]

不断重复此 *** 作，如果某个时刻 arr 为空，则说明 arr 可以满足题目要求。

代码实现时，我们可以用一个哈希表来统计 cnt，并将其键值按绝对值从小到大排序，然后模拟上述 *** 作，去掉元素的 *** 作可以改为从 cnt 中减去对应值。

2.sort() 函数的参数：

(1)参数一是要排序的数组的起始地址。

(2)参数二是结束的地址（最后一位要排序的地址）。

(3)参数三是排序的方法，可以是从大到小也可是从小到大，若不写第三个参数，则默认的排序方法是从小到大。

sort() 函数使用模板：sort(start, end, 排序方法);

class Solution {
public:
    bool canReorderDoubled(vector<int> &arr) {
        unordered_map<int, int> cnt;
        for (int x : arr) {
            ++cnt[x];
        }
        if (cnt[0] % 2) {
            return false;
        }

        vector<int> vals;
        vals.reserve(cnt.size());
        for (auto &[x, _] : cnt) {//取cnt的key
            vals.push_back(x);
        }//vals里面每个数字都是arr里面唯一的。


        sort(vals.begin(), vals.end(), [](int a, int b) { return abs(a) < abs(b); });//(bool)(abs(a) < abs(b))?a:b;按绝对值排序，小的排在前面

        for (int x : vals) {//每次取出的都是绝对值最小的，所以必须与2x配对
            if (cnt[2 * x] < cnt[x]) { // 无法找到足够的 2x 与 x 配对
                return false;
            }
            cnt[2 * x] -= cnt[x];
        }
        return true;
    }
};

复杂度分析

时间复杂度：O(nlogn)，其中 n 是数组arr 的长度。

最坏情况下哈希表中有 n 个元素，对其排序需要 O(nlogn) 的时间。

空间复杂度：O(n)。

最坏情况下哈希表中有 n 个元素，需要 O(n) 的空间。

解题思路二：用flag会超时！

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        int n=arr.size();
    //     1 3 5 7 9
    // 2*  0 2 4 6 8
    // 每个数必须找到一个其的2倍或1/2倍
        vector<int> flag(n);//访问数组
        sort(arr.begin(),arr.end());
        for(int i=0;i<n;++i){
            if(arr[i]==0&&!flag[i]){
                for(int j=i+1;j<n;j++){
                    if(arr[j]==0){
                        flag[i]=1;
                        flag[j]=1;
                        break;
                    }
                }
            }
            if(!flag[i]){//i未被访问
                for(int j=i+1;j<n;j++){
                    if(arr[i]%2==0){//偶数
                        if(!flag[j]&&(arr[j]==2*arr[i]||arr[j]==arr[i]/2)){//j未被访问且与i配对
                        flag[i]=1;
                        flag[j]=1;
                        break;
                        }
                    }else{
                        if(!flag[j]&&arr[j]==2*arr[i]){//j未被访问且与i配对
                        flag[i]=1;
                        flag[j]=1;
                        break;
                        }
                    }
                    
                }
            }else{
                continue;
            }
            if(!flag[i]){//没有与i配对的
                    return false;
            }
        }
        return true;
    }
};