You are given an integer array nums of size n and a positive integer k.

Divide the array into one or more arrays of size 3 satisfying the following conditions:

  • Each element of nums should be in exactly one array.
  • The difference between any two elements in one array is less than or equal to k.

Return a 2D array containing all the arrays. If it is impossible to satisfy the conditions, return an empty array. And if there are multiple answers, return any of them.

Example 1:

Input: nums = [1,3,4,8,7,9,3,5,1], k = 2 Output: [[1,1,3],[3,4,5],[7,8,9]] Explanation: We can divide the array into the following arrays: [1,1,3], [3,4,5], and [7,8,9]. The difference between any two elements in each array is less than or equal to 2. Note that the order of elements is not important.

Example 2:

Input: nums = [1,3,3,2,7,3], k = 3 Output: [] Explanation: It is not possible to divide the array satisfying all the conditions.

Constraints:

  • n == nums.length
  • 1 <= n <= 10^5
  • n is a multiple of 3.
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= 10^5

题目分析

Greedy, Sorting, Two pointers

代码实现

class Solution {
public:
    vector <vector <int>> ans;
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        if(nums.size()
        for(int i = 0, j = 2; i < nums.size();) {
            if(nums[j] - nums[i] > k) return {};
            vector <int> t;
            for(int k = i; k <= j; ++k) t.push_back(nums[k]);
            ans.push_back(t);
            i = j + 1, j += 3;
        }
        return ans;
    }
};
分类: GreedySortThought

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status