头像

wzc1995


访客:444230

离线:5小时前



wzc1995
5小时前

题目描述

有一块木板,长度为 n单位。一些蚂蚁在木板上移动,每只蚂蚁都以 每秒一个单位 的速度移动。其中,一部分蚂蚁向 移动,其他蚂蚁向 移动。

当两只向 不同 方向移动的蚂蚁在某个点相遇时,它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。

而当蚂蚁在某一时刻 t 到达木板的一端时,它立即从木板上掉下来。

给你一个整数 n 和两个整数数组 left 以及 right。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。

样例

ants.jpg

输入:n = 4, left = [4,3], right = [0,1]
输出:4
解释:如上图所示:
-下标 0 处的蚂蚁命名为 A 并向右移动。
-下标 1 处的蚂蚁命名为 B 并向右移动。
-下标 3 处的蚂蚁命名为 C 并向左移动。
-下标 4 处的蚂蚁命名为 D 并向左移动。
请注意,蚂蚁在木板上的最后时刻是 t = 4 秒,之后蚂蚁立即从木板上掉下来。
(也就是说在 t = 4.0000000001 时,木板上没有蚂蚁)。

ants2.jpg

输入:n = 7, left = [], right = [0,1,2,3,4,5,6,7]
输出:7
解释:所有蚂蚁都向右移动,下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。

ants3.jpg

输入:n = 7, left = [0,1,2,3,4,5,6,7], right = []
输出:7
解释:所有蚂蚁都向左移动,下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。
输入:n = 9, left = [5], right = [4]
输出:5
解释:t = 1 秒时,两只蚂蚁将回到初始位置,但移动方向与之前相反。
输入:n = 6, left = [6], right = [0]
输出:6

限制

  • 1 <= n <= 10^4
  • 0 <= left.length <= n + 1
  • 0 <= left[i] <= n
  • 0 <= right.length <= n + 1
  • 0 <= right[i] <= n
  • 1 <= left.length + right.length <= n + 1
  • leftright 中的所有值都是唯一的,并且每个值 只能出现在二者之一 中。

算法

(模拟) $O(n)$
  1. 两只蚂蚁相遇可以忽略,因为交换方向如果不考虑蚂蚁编号的话实际上等于没有交换。
  2. 对于向左走的蚂蚁,需要的时间等于初始的位置;对于向右走的蚂蚁,需要的时间等于长度减去初始位置。

时间复杂度

  • 分别遍历两个数组一次,时间复杂度为 $O(n)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int ans = 0;
        for (int x : left)
            ans = max(ans, x);

        for (int x : right)
            ans = max(ans, n - x);

        return ans;
    }
};



wzc1995
5小时前

题目描述

给你一个数字数组 arr

如果一个数列中,任意相邻两项的差总等于同一个常数,那么这个数列就称为 等差数列

如果可以重新排列数组形成等差数列,请返回 true;否则,返回 false

样例

输入:arr = [3,5,1]
输出:true
解释:对数组重新排序得到 [1,3,5] 或者 [5,3,1],
任意相邻两项的差分别为 2 或 -2,可以形成等差数列。
输入:arr = [1,2,4]
输出:false
解释:无法通过重新排序得到等差数列。

限制

  • 2 <= arr.length <= 1000
  • -10^6 <= arr[i] <= 10^6

算法

(排序) $O(n \log n)$
  1. 将原数组从小到大排序。
  2. 判断任意相邻两个数字的差值是否一致。

时间复杂度

  • 排序后遍历一次,故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());

        int n = arr.size(), d = arr[1] - arr[0];

        for (int i = 2; i < n; i++)
            if (arr[i] - arr[i - 1] != d)
                return false;

        return true;
    }
};



wzc1995
5天前

题目描述

给定一组 N 人(编号为 1, 2, ..., N),我们想把每个人分进任意大小的两组。

每个人都可能不喜欢其他人,那么他们不应该属于同一组。

形式上,如果 dislikes[i] = [a, b],表示不允许将编号为 ab 的人归入同一组。

当可以用这种方法将每个人分进两组时,返回 true;否则返回 false

样例

输入:N = 4, dislikes = [[1,2],[1,3],[2,4]]
输出:true
解释:group1 [1,4], group2 [2,3]
输入:N = 3, dislikes = [[1,2],[1,3],[2,3]]
输出:false
输入:N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出:false

限制

  • 1 <= N <= 2000
  • 0 <= dislikes.length <= 10000
  • dislikes[i].length == 2
  • 1 <= dislikes[i][j] <= N
  • dislikes[i][0] < dislikes[i][1]
  • 对于 dislikes[i] == dislikes[j] 不存在 i != j

算法

(二分图判定,黑白染色) $O(n + m)$
  1. 用黑白两种颜色对整个图进行染色,相邻的结点染不同的颜色。
  2. 如果过程中出现相邻两个结点颜色一样,则说明出现了奇环。
  3. 图论告诉我们有奇环的图不是二分图。

时间复杂度

  • 需要遍历整个图进行染色,故时间复杂度为 $O(n + m)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储遍历用的数据结构。

C++ 代码 (DFS)

class Solution {
private:
    bool dfs(int u, const vector<vector<int>> &graph, vector<int> &col) {
        for (int v : graph[u])
            if (col[v] == -1) {
                col[v] = 1 - col[u];
                if (!dfs(v, graph, col))
                    return false;
            } else if (col[v] == col[u])
                return false;

        return true;
    }
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(N);
        for (const auto &v : dislikes) {
            int x = v[0] - 1, y = v[1] - 1;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }

        vector<int> col(N, -1);

        for (int i = 0; i < N; i++)
            if (col[i] == -1) {
                col[i] = 0;
                if (!dfs(i, graph, col))
                    return false;
            }

        return true;
    }
};

C++ 代码 (BFS)

class Solution {
private:
    bool bfs(int S, const vector<vector<int>> &graph, vector<int> &col) {
        queue<int> q;

        q.push(S);
        col[S] = 0;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : graph[u]) {
                if (col[v] == col[u])
                    return false;
                if (col[v] == -1) {
                    col[v] = 1 - col[u];
                    q.push(v);
                }
            }
        }

        return true;
    }

public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(N);
        for (const auto &v : dislikes) {
            int x = v[0] - 1, y = v[1] - 1;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }

        vector<int> col(N, -1);

        for (int i = 0; i < N; i++)
            if (col[i] == -1)
                if (!bfs(i, graph, col))
                    return false;

        return true;
    }
};



wzc1995
5天前

题目描述

i 个人的体重为 people[i],每艘船可以承载的最大重量为 limit

每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

样例

输入:people = [1,2], limit = 3
输出:1
解释:1 艘船载 (1, 2)
输入:people = [3,2,2,1], limit = 3
输出:3
解释:3 艘船分别载 (1, 2), (2) 和 (3)
输入:people = [3,5,3,4], limit = 5
输出:4
解释:4 艘船分别载 (3), (3), (4), (5)

限制

  • 1 <= people.length <= 50000
  • 1 <= people[i] <= limit <= 30000

算法

(贪心) $O(n \log n)$
  1. 将人按重量排序。
  2. 如果当前最重的人和当前最轻的人能坐到一条船上,则他们坐一条船。否则当前最重的人单独坐一条船走。

时间复杂度

  • 排序的时间复杂度为 $O(n \log n)$。
  • 排序后,每个人仅需要遍历一次,故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());

        int i = 0, j = people.size() - 1, ans = 0;
        while (i <= j) {
            if (i != j && people[i] + people[j] <= limit)
                i++;

            j--;
            ans++;
        }

        return ans;
    }
};



wzc1995
5天前

题目描述

珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K(单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 KK 为整数)。

样例

输入:piles = [3,6,7,11], H = 8
输出:4
输入:piles = [30,11,23,4,20], H = 5
输出:30
输入:piles = [30,11,23,4,20], H = 6
输出:23

限制

  • 1 <= piles.length <= 10^4
  • piles.length <= H <= 10^9
  • 1 <= piles[i] <= 10^9

算法

(二分答案) $O(n \log M)$
  1. 注意到 K 越小,所花费的时间越长,我们要找到一个最小的 K 满足花费的时间小于等于 H
  2. 二分查找这个 K 值,如果花费的时间小于等于 H,我们就继续减小 K。否则我们增大 K。二分的范围从 1 到数组中的最大值 $M$。

时间复杂度

  • 二分的次数为 $O(\log M)$。
  • 每次二分需要线性的时间判定,故总时间复杂度为 $O(n \log M)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    int calc(int k, const vector<int> &piles) {
        int tot = 0;
        for (int x : piles)
            tot += x / k + (bool)(x % k);

        return tot;
    }

public:
    int minEatingSpeed(vector<int>& piles, int H) {
        int n = piles.size();
        int l = 1;
        int r = *max_element(piles.begin(), piles.end());

        while (l < r) {
            int mid = (l + r) >> 1;
            if (calc(mid, piles) <= H) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};



wzc1995
5天前

题目描述

如果序列 X_1, X_2, ..., X_n 满足下列条件,就说它是 斐波那契式 的:

  • n >= 3
  • 对于所有 i + 2 <= n,都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列,找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在,返回 0

(回想一下,子序列是从原序列 A 中派生出来的,它从 A 中删掉任意数量的元素(也可以不删),而不改变其余元素的顺序。例如,[3, 5, 8][3, 4, 5, 6, 7, 8] 的一个子序列)

样例

输入:[1,2,3,4,5,6,7,8]
输出:5
解释:
最长的斐波那契式子序列为:[1,2,3,5,8]。
输入:[1,3,7,11,12,14,18]
输出:3
解释:
最长的斐波那契式子序列有:
[1,11,12],[3,11,14] 以及 [7,11,18]。

限制

  • 3 <= A.length <= 1000
  • 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
    *(对于以 Java,C,C++,以及 C# 的提交,时间限制被减少了 50%)

算法1

(暴力枚举) $O(n^2 \log M)$
  1. 枚举斐波那契数列的前两个数字,然后用集合暴力判定数列能延续的长度。
  2. 因为斐波那契数列上升是指数级的,所以答案最多不超过 $O(\log M)$,其中 $M$ 是最大的数字。
  3. 我们可以加上一个剪枝,如果第一个数字的 ans + 2 倍超过了数组中最大的数字,则此次判定必定不会超过当前答案。

时间复杂度

  • 枚举开头两个数字的时间复杂度为 $O(n^2)$。
  • 暴力判定的时间复杂度为 $O(\log M)$。
  • 故总时间复杂度为 $O(n^2 \log M)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储集合。

C++ 代码

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        unordered_set<int> nums(A.begin(), A.end());
        int n = A.size();

        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int x = A[i], y = A[j];

                if ((long long)(x) * (ans + 2) > A.back())
                    continue;

                int cnt = 0;
                while (nums.find(x + y) != nums.end()) {
                    cnt++;
                    int t = x + y;
                    x = y; y = t;
                }

                ans = max(ans, cnt);
            }

        return ans == 0 ? 0 : ans + 2;
    }
};

算法2

(动态规划) $O(n^2)$
  1. 设状态 $f(i, j)$ 表示以 nums[i]nums[j] 结尾的斐波那契数列的最大长度,其中 $i < j$。
  2. 初始化全部为 0。
  3. 转移时,如果存在一个下标 $k$,满足 $k < i$ 且 $nums[k] = nums[j] - nums[i]$,则转移 $f(i, j) = f(k, i) + 1$,这一步可以用哈希表判定。
  4. 最终答案为 $f$ 数组中的最大值。

时间复杂度

  • 状态数为 $O(n^2)$,每次转移仅需要常数时间,故总时间复杂度为 $O(n^2)$。

空间复杂度

  • 需要 $O(n^2)$ 的额外空间存储哈希表和动态规划的状态。

C++ 代码

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> f(n, vector<int>(n, 0));

        unordered_map<int, int> mp;
        for (int i = 0; i < n; i++)
            mp[A[i]] = i;

        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int d = A[j] - A[i];
                if (mp.find(d) != mp.end() && mp[d] < i) {
                    f[i][j] = f[mp[d]][i] + 1;
                    ans = max(ans, f[i][j]);
                }
            }

        return ans == 0 ? 0 : ans + 2;
    }
};



wzc1995
5天前

题目描述

给定两个大小相等的数组 ABA 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列,使其相对于 B 的优势最大化。

样例

输入:A = [2,7,11,15], B = [1,10,4,11]
输出:[2,11,7,15]
输入:A = [12,24,8,32], B = [13,25,32,11]
输出:[24,32,8,12]

限制

  • 1 <= A.length = B.length <= 10000
  • 0 <= A[i] <= 10^9
  • 0 <= B[i] <= 10^9

算法

(贪心) $O(n \log n)$
  1. AB 数组从小到大排序。
  2. B 数组上定义双指针 lr,初始时 l = 0r = n - 1。如果当前 A[i] > B[l],则我们就这样安排,否则我们安排当前 B 最大的数字。
  3. 贪心的正确性是 A 中的每个数字都要尽可能的干掉 B 中的一个数字,如果干不掉,则消耗掉 B 中剩余最大的数字。

时间复杂度

  • 排序的时间复杂度为 $O(n \log n)$。
  • 安排数字的时间复杂度为 $O(n)$。
  • 故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储 B 数组的索引和答案。

C++ 代码

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> idx(n);

        for (int i = 0; i < n; i++)
            idx[i] = i;

        sort(A.begin(), A.end());
        sort(idx.begin(), idx.end(), [&](int x, int y) {
            return B[x] < B[y];
        });

        vector<int> ans(n);

        for (int i = 0, l = 0, r = n - 1; i < n; i++) {
            if (A[i] > B[idx[l]]) ans[idx[l++]] = A[i];
            else ans[idx[r--]] = A[i];
        }

        return ans;
    }
};



wzc1995
7天前

题目描述

给定一个数组 points 和一个整数 k。数组中每个元素都表示二维平面上的点的坐标,并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [x_i, y_i],并且在 1 <= i < j <= points.length 的前提下,x_i < x_j 总成立。

请你找出 y_i + y_j + |x_i - x_j|最大值,其中 |x_i - x_j| <= k1 <= i < j <= points.length

题目测试数据保证至少存在一对能够满足 |x_i - x_j| <= k 的点。

样例

输入:points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
输出:4
解释:前两个点满足 |xi - xj| <= 1 ,带入方程计算,则得到值 3 + 0 + |1 - 2| = 4。
第三个和第四个点也满足条件,得到值 10 + -10 + |5 - 6| = 1。
没有其他满足条件的点,所以返回 4 和 1 中最大的那个。
输入:points = [[0,0],[3,0],[9,2]], k = 3
输出:3
解释:只有前两个点满足 x 坐标差的绝对值小于 3,带入后得到值 0 + 0 + |0 - 3| = 3。

限制

  • 2 <= points.length <= 10^5
  • points[i].length == 2
  • -10^8 <= points[i][0], points[i][1] <= 10^8
  • 0 <= k <= 2 * 10^8
  • 对于所有的 1 <= i < j <= points.lengthpoints[i][0] < points[j][0] 都成立。
  • x_i 是严格递增的。

算法

(单调队列) $O(n)$
  1. 假定 $x_i < x_j$,将原方程进行变形,得到 $(y_i - x_i) + (y_j + x_j)$。可以枚举每一个 $y_j + x_j$,找到 $i < j$,使得 $y_i - x_i$ 尽可能大。
  2. 维护一个从队头到队尾严格单调递减的队列,队列中存下标。
  3. 如果当前队头元素不满足限制,则队头不断出队。
  4. 如果队列非空,则用队头更新答案。
  5. 如果当前 $y_j - x_j$ 大于等于队尾,则队尾不断出队,因为出队的元素都不如 $j$ 更优。
  6. 最后 $j$ 入队。

时间复杂度

  • 每个位置最多入队一次,出队一次,故时间复杂度为 $O(n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储队列。

C++ 代码

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        int n = points.size();
        deque<int> q;
        int ans = INT_MIN;

        for (int j = 0; j < n; j++) {
            int xj = points[j][0], yj = points[j][1];

            while (!q.empty() && xj - points[q.front()][0] > k)
                q.pop_front();

            if (!q.empty()) {
                int i = q.front();
                ans = max(ans, points[i][1] - points[i][0] + yj + xj);
            }

            while (!q.empty() && yj - xj >= points[q.back()][1] - points[q.back()][0])
                q.pop_back();

            q.push_back(j);
        }

        return ans;
    }
};



wzc1995
7天前

题目描述

给定一个整数数组 nums 和一个整数 target

请你统计并返回 nums 中能满足其最小元素与最大元素的 小于或等于 target非空 子序列的数目。

由于答案可能很大,请将结果对 10^9 + 7 取余后返回。

样例

输入:nums = [3,5,6,7], target = 9
输出:4
解释:有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)
输入:nums = [3,3,6,8], target = 10
输出:6
解释:有 6 个子序列满足该条件。(nums 中可以有重复数字)
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
输入:nums = [2,3,3,4,6,7], target = 12
输出:61
解释:共有 63 个非空子序列,其中 2 个不满足条件([6,7], [7])
有效序列总数为(63 - 2 = 61)
输入:nums = [5,2,4,1,7,6,8], target = 16
输出:127
解释:所有非空子序列都满足条件 (2^7 - 1) = 127

限制

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6
  • 1 <= target <= 10^6

算法1

(二分) $O(n \log n)$
  1. 将数组从小到大排序。对于每个位置 $i$,二分查询最小的位置 $l <= i$,满足 nums[i] + nums[l] > target。如果 $m$ 不存在则令 $l := n$。
  2. 对于最小值 nums[i],我们可选的最大值有 nums[i]nums[i + 1] 一直到 nums[l - 1]
  3. 如果 $l > i$,则可选的方案数为 $1 + 2^0 + \dots + 2^{l - i - 2} = 2^{l - i - 1}$。

时间复杂度

  • 排序的时间复杂度为 $O(n \log n)$。
  • 对于每个位置,二分的时间复杂度为 $O(\log n)$。
  • 故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 需要额外 $O(n)$ 的空间存储预处理的 2 的幂次。

C++ 代码

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        const int mod = 1000000007;

        sort(nums.begin(), nums.end());

        int n = nums.size();

        vector<int> power(n);
        power[0] = 1;

        for (int i = 1; i < n; i++)
            power[i] = power[i - 1] * 2 % mod;

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int l = i, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (nums[i] + nums[mid] <= target)
                    l = mid + 1;
                else
                    r = mid;
            }

            if (l > i)
                ans = (ans + power[l - i - 1]) % mod;
        }

        return ans;
    }
};

算法2

(双指针) $O(n)$
  1. 将数组从小到大排序。
  2. 仿照 Two Sum 的双指针解法,初始时固定 $l := 0$,$r := n - 1$。
  3. 在 $l \le r$ 的情况下,如果 nums[l] + nums[r] <= target,则 $l$ 自加。否则 $r$ 自减。
  4. 注意到,当 nums[l] + nums[r] <= target 成立时,对于 nums[l] 来说,nums[r] 是最大可选的最大值。
  5. 也就是说对于最小值 nums[l],可选的最大值有 nums[l]nums[l + 1] 一直到 nums[r]
  6. 故可选的方案数为 $1 + 2^0 + 2^1 + \dots + 2^{r - l - 1} = 2^{r - l}$。

时间复杂度

  • 排序的时间复杂度为 $O(n \log n)$。
  • 排序后双指针每个位置仅被遍历一次。
  • 故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 需要额外 $O(n)$ 的空间存储预处理的 2 的幂次。

C++ 代码

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        const int mod = 1000000007;

        sort(nums.begin(), nums.end());

        int n = nums.size();
        vector<int> power(n);

        power[0] = 1;
        for (int i = 1; i < n; i++)
            power[i] = power[i - 1] * 2 % mod;

        int ans = 0;
        int l = 0, r = n - 1;

        while (l <= r) {
            if (nums[l] + nums[r] <= target) {
                ans = (ans + power[r - l]) % mod;
                l++;
            } else {
                r--;
            }
        }

        return ans;
    }
};



wzc1995
7天前

题目描述

给定一个整数数组 arr 和一个整数 k,其中数组长度是偶数,值为 n

现在需要把数组恰好分成 n / 2 对,以使每对数字的和都能够被 k 整除。

如果存在这样的分法,请返回 True;否则,返回 False

样例

输入:arr = [1,2,3,4,5,10,6,7,8,9], k = 5
输出:true
解释:划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10)。
输入:arr = [1,2,3,4,5,6], k = 7
输出:true
解释:划分后的数字对为 (1,6),(2,5) 以及 (3,4)。
输入:arr = [1,2,3,4,5,6], k = 10
输出:false
解释:无法在将数组中的数字分为三对的同时满足每对数字和能够被 10 整除的条件。
输入:arr = [-10,10], k = 2
输出:true
输入:arr = [-1,1,-2,2,-3,3,-4,4], k = 3
输出:true

限制

  • arr.length == n
  • 1 <= n <= 10^5
  • n 为偶数
  • -10^9 <= arr[i] <= 10^9
  • 1 <= k <= 10^5

算法

(数学) $O(n + k)$
  1. 将原数组中的元素按照模 $k$ 的余数分类,统计余数为 0 到 k-1 的个数。
  2. 如果余数为 0 的个数不为偶数,则返回 false
  3. 接下来判定余数为 ik - i 的个数是否相等。如果 i == k - i,则需要判定余数为 i 的个数是否为偶数。

时间复杂度

  • 遍历一次原数组,然后遍历一次余数数组,时间复杂度为 $O(n + k)$。

空间复杂度

  • 需要额外 $O(k)$ 的空间存储每个余数的个数。

C++ 代码

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        vector<int> r(k, 0);
        for (int x : arr)
            r[(x % k + k) % k]++;

        if (r[0] % 2 != 0)
            return false;

        for (int i = 1, j = k - 1; i <= j; i++, j--) {
            if (i == j) {
                if (r[i] % 2 != 0)
                    return false;
            } else {
                if (r[i] != r[j])
                    return false;
            }
        }

        return true;
    }
};