[LeetCode] 1282. Group the People Given the Group Size They Belong To 用户分组([LeetCode] 1282. Group the People Given the Group Size They Belong To User grouping)

There are  people that are split into some unknown number of groups. Each person is labeled with a unique ID from  to .

n
0
n - 1

You are given an integer array , where  is the size of the group that person  is in. For example, if , then person  must be in a group of size .

groupSizes
groupSizes[i]
i
groupSizes[1] = 3
1
3

Return a list of groups such that each person  is in a group of size .

i
groupSizes[i]

Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers, return any of them. It is guaranteed that there will be at least one valid solution for the given input.

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation:
The first group is [5]. The size is 1, and groupSizes[5] = 1.
The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

Constraints:

  • groupSizes.length == n
  • 1 <= n <= 500
  • 1 <= groupSizes[i] <= n

这道题说是将n个人(编号为0到 n-1)分为若干个组,现在给了一个 groupSizes 数组,其中 groupSizes[i] 是编号为i的人所在的组的总人数,现在让返回分成的这些组,并将该组的人的编号放进去。通过分析例子不难理解题意,例子1中,一堆3中间有一个有一个1,其位置是5,那么很显然,编号为5的人,单独是一组,那么博主就想到,应该是先处理人数少的组,则可以对总人数排序,但是由于编号信息不能丢失,所以可以建立组人数和编号的 pair 对儿,然后放到一个新数组 all 中,然后对 all 进行排序,默认是以 pair 对儿中的第一个元素为 key 进行排序,即是按照组人数从小到大排序。这样就可以开始处理了,取出当前的组人数 cnt,然后新建一个数组 out,变量j从0遍历到 cnt,然后将 all[i+j][1] 加入数组 out 中,即把对应的编号加入。因为组人数是有序的,所以若当前是 cnt,则之后 cnt 个数字一定都等于 cnt,所以可以按顺序加入到 out 数组中,然后将 out 加入结果 res,此时要更新变量i,将其加上 cnt-1,因为 for 循环本身还要再加1,参见代码如下:

解法一:

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> res, all;
        int n = groupSizes.size();
        for (int i = 0; i < n; ++i) {
            all.push_back({groupSizes[i], i});
        }
        sort(all.begin(), all.end());
        for (int i = 0; i < n; ++i) {
            int cnt = all[i][0];
            vector<int> out;
            for (int j = 0; j < cnt; ++j) {
                out.push_back(all[i + j][1]);
            }
            res.push_back(out);
            i += cnt - 1;
        }
        return res;
    }
};

上面的方法虽然 work,但也是险过,说不定哪天就被 OJ 排除在外了,这道题其实有更简单高效的解法。并不需要排序,而是将所在群组人数相同的人归类到一起,这样可以使用一个二维数组 all,其中 all[i] 表示所在群组个数为i的人的编号的集合,大小初始化为 n+1,其中n是 groupSizes 的大小。然后i从0遍历到 n-1,将编号i放入 all[groupSizes[i]] 中,因为 groupSizes[i] 是编号为i的人所在的群组的人数,外面套个 all,就是具有相同群组人数的人的集合,若等于 groupSizes[i],说明此时的群组已经放满了,可以加入到结果 res 中,然后将其清空,以便给放之后符合条件的人,参见代码如下:

解法二:

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        int n = groupSizes.size();
        vector<vector<int>> res, all(n + 1);
        for (int i = 0; i < n; ++i) {
            all[groupSizes[i]].push_back(i);
            if (all[groupSizes[i]].size() == groupSizes[i]) {
                res.push_back(all[groupSizes[i]]);
                all[groupSizes[i]].clear();
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1282

参考资料:

https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/

https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/discuss/446534/C%2B%2BJava-Greedy

LeetCode All in One 题目讲解汇总(持续更新中…)

————————

There are  people that are split into some unknown number of groups. Each person is labeled with a unique ID from  to .

n
0
n - 1

You are given an integer array , where  is the size of the group that person  is in. For example, if , then person  must be in a group of size .

groupSizes
groupSizes[i]
i
groupSizes[1] = 3
1
3

Return a list of groups such that each person  is in a group of size .

i
groupSizes[i]

Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers, return any of them. It is guaranteed that there will be at least one valid solution for the given input.

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation:
The first group is [5]. The size is 1, and groupSizes[5] = 1.
The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

Constraints:

  • groupSizes.length == n
  • 1 <= n <= 500
  • 1 <= groupSizes[i] <= n

The problem is to divide n individuals (numbered 0 to n-1) into several groups. Now we give an array of groupsizes, where groupsizes [i] is the total number of people in the group where the person numbered I belongs. Now let’s return these groups and put the number of people in the group. By analyzing the example, it is not difficult to understand the meaning of the question. In example 1, there is a 1 in the middle of a pile of 3, and its position is 5. Obviously, the person numbered 5 is a separate group, so the blogger thinks that the group with a small number of people should be processed first, and the total number can be sorted. However, since the number information cannot be lost, a pair pair of group number and number can be established, Then put it into a new array all and sort all. By default, the first element in the pair pair is used as the key to sort, that is, sort according to the number of groups from small to large. In this way, you can start processing. Take out the current group number CNT, and then create an array out. The variable J traverses from 0 to CNT, and then add all [i + J] [1] to the array out, that is, add the corresponding number. Because the number of people in the group is in order, if the current is CNT, then the next CNT numbers must be equal to CNT, so you can add them to the out array in order, and then add out to the result res. at this time, you need to update the variable I and add cnt-1, because the for loop itself needs to add 1. See the code below:

Solution 1:

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> res, all;
        int n = groupSizes.size();
        for (int i = 0; i < n; ++i) {
            all.push_back({groupSizes[i], i});
        }
        sort(all.begin(), all.end());
        for (int i = 0; i < n; ++i) {
            int cnt = all[i][0];
            vector<int> out;
            for (int j = 0; j < cnt; ++j) {
                out.push_back(all[i + j][1]);
            }
            res.push_back(out);
            i += cnt - 1;
        }
        return res;
    }
};

Although the above method works, it is also dangerous. Maybe OJ will exclude it one day. In fact, there is a simpler and more efficient solution to this problem. Instead of sorting, people in the same group are grouped together. In this way, a two-dimensional array all can be used, where all [i] represents the collection of numbers of people in the group I, and the size is initialized to N + 1, where n is the size of groupsizes. Then I traverses from 0 to n-1, and puts the number I into all [groupsizes [i]], because groupsizes [i] is the number of people in the group where the person with the number I belongs. Set all outside, it is the collection of people with the same number of groups. If it is equal to groupsizes [i], it means that the group is full at this time. You can add it to the result res and empty it, For those who meet the conditions after release, see the code as follows:

Solution 2:

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        int n = groupSizes.size();
        vector<vector<int>> res, all(n + 1);
        for (int i = 0; i < n; ++i) {
            all[groupSizes[i]].push_back(i);
            if (all[groupSizes[i]].size() == groupSizes[i]) {
                res.push_back(all[groupSizes[i]]);
                all[groupSizes[i]].clear();
            }
        }
        return res;
    }
};

GitHub sync address:

https://github.com/grandyang/leetcode/issues/1282

reference material:

https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/

https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/discuss/446534/C%2B%2BJava-Greedy

Leetcode all in one topic explanation summary (under continuous update…)