Java&C++题解与拓展——leetcode954.二倍数对数组(父子对)【拓扑排序,priority

Java&C++题解与拓展——leetcode954.二倍数对数组(父子对)【拓扑排序,priority,第1张

每日一题做题记录,参考官方和三叶的题解

目录
  • 题目要求
    • 理解
  • 思路:逐一判断with优先队列
    • Java
    • C++
      • priority_queue自定义排序
  • 思路:成对构造
    • Java
    • C++
  • 思路:拓扑排序
    • Java
      • 拓扑排序
    • C++
      • queue
  • 思路四:双指针
    • Java
    • C++
  • 总结

题目要求

理解

一个找父子对的过程,每个孩子都有爸就true,缺爸缺孩子就false


思路:逐一判断with优先队列

遍历每一个值,找它在数组里的爸爸。



遍历顺序:从最接近 0 0 0的值开始,即对绝对值排序。



采用优先队列实现以与 0 0 0的距离为基准的小根堆,开始遍历:

  • 当前值 x x x没有儿子,则只能当儿子,给它找一个爸 x ∗ 2 x*2 x2,对 s o n [ x ∗ 2 ] son[x*2] son[x2]加一;
  • 当前值 x x x有儿子,说明可以和之前的数 x 2 \frac{x}{2} 2x组成父子对,则 s o n [ x ] son[x] son[x]减一。


遍历完成后,所有值的儿子数量均为 0 0 0,则原数组可以构成 n 2 \frac{n}{2} 2n个父子对。


【由于同时存在负数和乘二 *** 作,需对结果进行偏移 *** 作,即给每个结果加上 2 ∗ 1 0 5 2*10^5 2105

Java
class Solution {
    static int N = 100001;
    static int M = N * 2; //矫正数据范围
    static int[] son = new int[M * 2]; //儿子数量
    public boolean canReorderDoubled(int[] arr) {
        Arrays.fill(son, 0);
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> Math.abs(a) - Math.abs(b));
        for(int i : arr)
            pq.add(i);
        while(!pq.isEmpty()) {
            int x = pq.poll(), t = x * 2;
            if(son[x + M] != 0 && --son[x + M] >= 0)
                continue;
            son[t + M]++;
        }
        for(int i = 0; i < M * 2; i++)
            if(son[i] != 0)
                return false;
        return true;
    }
}
  • 时间复杂度: O ( n log ⁡ n + m ) O(n\log n + m) O(nlogn+m) n n n a r r arr arr长度, m m m a r r [ i ] arr[i] arr[i]的值域范围,将所有值放入优先队列和取出的复杂度均为 O ( n log ⁡ n ) O(n\log n) O(nlogn),检查是否存在合法结果的复杂度为 O ( m ) O(m) O(m)
  • 空间复杂度: O ( m + n ) O(m+n) O(m+n)
C++
class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        int N = 100001;
        int M = N * 2; //矫正数据范围
        int son[M * 2]; //儿子数量

        memset(son, 0, sizeof(son));
        auto cmp = [](int a, int b) { return abs(a) > abs(b); };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        for(int i : arr)
            pq.push(i);

        while(!pq.empty()) {
            int x = pq.top(), t = x * 2;
            cout << x <<endl;
            pq.pop();
            if(son[x + M] != 0 && --son[x + M] >= 0)
                continue;
            son[t + M]++;
        }
        for(int i = 0; i < M * 2; i++)
            if(son[i] != 0)
                return false;
        return true;
    }
};
  • 时间复杂度: O ( n log ⁡ n + m ) O(n\log n + m) O(nlogn+m)
  • 空间复杂度: O ( m + n ) O(m+n) O(m+n)
priority_queue自定义排序
  • 学习参考链接
  • 此处用了lambda表达式。


思路:成对构造

要组成父子对,所以直接成对得消除等量的父子。


所以预处理一下所有的值出现的次数 c n t s cnts cnts并进行去重,然后按顺序一边构造父子对一边检查合法性。


Java
class Solution {
    static int N = 100001;
    static int M = N * 2; //矫正数据范围
    static int[] cnts = new int[M * 2];
    public boolean canReorderDoubled(int[] arr) {
        Arrays.fill(cnts, 0);
        List<Integer> list = new ArrayList<>();
        for(int i : arr)
            if(++cnts[i + M] == 1)
                list.add(i);
        Collections.sort(list, (a,b) -> Math.abs(a) - Math.abs(b)); //排序
        for(int i : list) {
            if(cnts[i * 2 + M] < cnts[i + M]) //不够组对
                return false;
            cnts[i * 2 + M] -= cnts[i + M]; //减去可组对项
        } 
        return true;
    }
}
  • 时间复杂度: O ( n log ⁡ n ) O(n\log n) O(nlogn),统计出现次数并去重的复杂度为 O ( n ) O(n) O(n),对去重数组排序复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn),构造并检查合法性复杂度为 O ( n ) O(n) O(n)
  • 空间复杂度: O ( m + n ) O(m+n) O(m+n)
C++
class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        int N = 100001;
        int M = N * 2; //矫正数据范围
        int cnts[M * 2];

        memset(cnts, 0, sizeof(cnts));
        vector<int> list;
        for(int i : arr)
            if(++cnts[i + M] == 1)
                list.push_back(i);
        sort(list.begin(), list.end(), [](int a, int b) { return abs(a) < abs(b); });

        for(int i : list) {
            if(cnts[i * 2 + M] < cnts[i + M]) //不够组对
                return false;
            cnts[i * 2 + M] -= cnts[i + M]; //减去可组对项
        }
        return true;
    }
};
  • 时间复杂度: O ( n log ⁡ n ) O(n\log n) O(nlogn)
  • 空间复杂度: O ( m + n ) O(m+n) O(m+n)
思路:拓扑排序

由于一个值只能和爸爸 2 ∗ x 2*x 2x或儿子 x 2 \frac{x}{2} 2x组对,那么可以基于此建一个由儿子指向爸爸的图,通过拓扑排序来验证结果。


那么进行数量统计和去重之后:

  • 当前值 x x x可以有儿子(为偶数),那令其入度为儿子数 i n [ x ] = c n t s [ x 2 ] in[x]=cnts[\frac{x}{2}] in[x]=cnts[2x]


    入度为 0 0 0时,说明没有儿子与之成对,那它只能做儿子,加入儿子队列;

  • 当前值 x x x不会有儿子(为奇数),那么它入度必为 0 0 0,加入儿子队列。


过程中要特殊处理只能和自己组对的 0 0 0,不把它放进图里,避免成环。


执行拓扑排序过程,设当前出队值为 t t t,此时需消耗掉 c n t [ t ] cnt[t] cnt[t]个爸爸 t ∗ 2 t*2 t2与之配对,同时更新爸爸的入度,若其入度为 0 0 0且还有剩余,那么说明它没有儿子可以配对了,将该爸爸加入儿子队列。


由于消耗了该爸爸数量,那需要同步更新爷爷 t ∗ 4 t*4 t4的入度,那同样爷爷若是入度也消耗为 0 0 0了,则也加入儿子队列。


Java
class Solution {
    static int N = 100001;
    static int M = N * 2; //矫正数据范围
    static int[] cnts = new int[M * 2], in = new int[M * 2];
    public boolean canReorderDoubled(int[] arr) {
        Arrays.fill(cnts, 0);
        Arrays.fill(in, 0);
        List<Integer> list = new ArrayList<>();
        for(int i : arr)
            if(++cnts[i + M] == 1 && i != 0) //0会成环
                list.add(i);
        if(cnts[M] % 2 != 0) //0和自己无法成对
            return false;
        
        Deque<Integer> son = new ArrayDeque<>(); //儿子队伍
        for(int i : list) {
            if(i % 2 == 0) { //偶数
                in[i + M] = cnts[i / 2 + M]; //入度为儿子数
                if(in[i + M] == 0)
                    son.addLast(i);
            }
            else
                son.addLast(i);
        }
        while(!son.isEmpty()) {
            int t = son.pollFirst();
            if(cnts[t * 2 + M] < cnts[t + M]) //儿子比爸多
                return false;
            cnts[t * 2 + M] -= cnts[t + M]; //减掉儿子数量
            in[t * 2 + M] -= cnts[t + M];
            if(in[t * 2 + M] == 0 && cnts[t * 2 + M] != 0)
                son.addLast(t * 2);
            in[t * 4 + M] -= cnts[t + M];
            if(in[t * 4 + M] == 0 && cnts[t * 4 + M] != 0)
                son.addLast(t * 4);
        }
        return true;
    }
}
  • 时间复杂度: O ( n ) O(n) O(n),统计 c n t s cnts cnts i n in in的复杂度是 O ( n ) O(n) O(n),拓扑序验证复杂度也是 O ( n ) O(n) O(n)
  • 空间复杂度: O ( n + m ) O(n+m) O(n+m)
拓扑排序
  • 学习参考链接
  • 对有向图构造拓扑序列的过程,有向无环图才能进行拓扑排序。


  • 删除入度为0的点,并对其他点更新。


C++
class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        int N = 100001;
        int M = N * 2; //矫正数据范围
        int cnts[M * 2], in[M * 2];
        memset(cnts, 0, sizeof(cnts));
        memset(in, 0, sizeof(in));
        vector<int> list;
        for(int i : arr)
            if(++cnts[i + M] == 1 && i != 0) //0会成环
                list.push_back(i);
        if(cnts[M] % 2 != 0) //0和自己无法成对
            return false;
        
        queue<int> son;
        for(int i : list) {
            if(i % 2 == 0) { //偶数
                in[i + M] = cnts[i / 2 + M]; //入度为儿子数
                if(in[i + M] == 0)
                    son.push(i);
            }
            else
                son.push(i);
        }
        while(!son.empty()) {
            int t = son.front();
            son.pop();
            if(cnts[t * 2 + M] < cnts[t + M]) //儿子比爸多
                return false;
            cnts[t * 2 + M] -= cnts[t + M]; //减掉儿子数量
            in[t * 2 + M] -= cnts[t + M];
            if(in[t * 2 + M] == 0 && cnts[t * 2 + M] != 0)
                son.push(t * 2);
            in[t * 4 + M] -= cnts[t + M];
            if(in[t * 4 + M] == 0 && cnts[t * 4 + M] != 0)
                son.push(t * 4);
        }
        return true;
    }
};
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( m + n ) O(m+n) O(m+n)
queue
  • 学习参考链接
  • 一个队列容器,和stack差不多。


思路四:双指针

【思来想去还是觉得这方法能用,花了好半天给他撕出来了,感觉是时空复杂度最佳的方法。



排序后注意负数和正数的爸爸和儿子相反,负数在找儿子,正数在找爸爸。


Java
class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length, len = 0;
        for(int i = 0; i < n; i++) {
            if(arr[i] >= 0) { //统计负数数量
                len = i;
                break;
            }
        }        
        if((len & 1) != 0) //奇数个
            return false;

        boolean[] used = new boolean[n];
        return check(arr, used, 0, len) && check(arr, used, len, n);
    }

    public static boolean check(int[] arr, boolean[] used, int sta, int end) {
        int l = sta, r = l + 1;
        while(l < end) {
            if(used[l]) { //已组过对
                l++;
                continue;
            }
            if(l >= r)
                r = l + 1;
            
            //负数l为爸爸,正数r为爸爸
            while(r < end && ((arr[r] < 0 && 2 * arr[r] < arr[l]) || (arr[r] > 0 && arr[r] < 2 * arr[l])))
                r++; //向右滑动直至可以匹配
            if(r == end || ((arr[r] < 0 && 2 * arr[r] > arr[l]) || (arr[r] > 0 && arr[r] > 2 * arr[l])))
                return false;

            used[r] = true; //标记组过对
            l++;
            r++;
        }
        return true;
    }
}
  • 时间复杂度: O ( n log ⁡ n ) O(n\log n) O(nlogn)
  • 空间复杂度: O ( n ) O(n) O(n)
C++
class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int n = arr.size(), len = 0;
        for(int i = 0; i < n; i++) {
            if(arr[i] >= 0) { //统计负数数量
                len = i;
                break;
            }
        }        
        if((len & 1) != 0) //奇数个
            return false;

        vector<bool> used;
        used.resize(arr.size());
        return check(arr, used, 0, len) && check(arr, used, len, n);
    }

    static bool check(vector<int>& arr, vector<bool>& used, int sta, int end) {
        int l = sta, r = l + 1;
        while(l < end) {
            if(used[l]) { //已组过对
                l++;
                continue;
            }
            if(l >= r)
                r = l + 1;
            
            //负数l为爸爸,正数r为爸爸
            while(r < end && ((arr[r] < 0 && 2 * arr[r] < arr[l]) || (arr[r] > 0 && arr[r] < 2 * arr[l])))
                r++; //向右滑动直至可以匹配
            if(r == end || ((arr[r] < 0 && 2 * arr[r] > arr[l]) || (arr[r] > 0 && arr[r] > 2 * arr[l])))
                return false;

            used[r] = true; //标记组过对
            l++;
            r++;
        }
        return true;
    }
};
  • 时间复杂度: O ( n log ⁡ n ) O(n\log n) O(nlogn)
  • 空间复杂度: O ( n ) O(n) O(n)
总结

这道题解决方法好多,除了文中的还看到有暴力哈希表统计(低配思路一)、贪心向上遍历、匹配模式等,但是今天事有点多,就不一一整理考虑了。



今天的收获是认真看了下拓扑排序。



但是太忙了,C++没认真搞好,改天回来给他结束掉。



欢迎指正与讨论!

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/562695.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-02
下一篇 2022-04-02

发表评论

登录后才能评论

评论列表(0条)

保存