[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)-其他

[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 = 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: [,[0,1,2],[3,4,6]]
Explanation:
The first group is . The size is 1, and groupSizes = 1.
The second group is [0,1,2]. The size is 3, and groupSizes = groupSizes = groupSizes = 3.
The third group is [3,4,6]. The size is 3, and groupSizes = groupSizes = groupSizes = 3.
Other possible solutions are [[2,1,6],,[0,4,3]] and [,[0,6,2],[4,3,1]].

Example 2:

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

Constraints:

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

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];
vector<int> out;
for (int j = 0; j < cnt; ++j) {
out.push_back(all[i + j]);
}
res.push_back(out);
i += cnt - 1;
}
return 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 = 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: [,[0,1,2],[3,4,6]]
Explanation:
The first group is . The size is 1, and groupSizes = 1.
The second group is [0,1,2]. The size is 3, and groupSizes = groupSizes = groupSizes = 3.
The third group is [3,4,6]. The size is 3, and groupSizes = groupSizes = groupSizes = 3.
Other possible solutions are [[2,1,6],,[0,4,3]] and [,[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2]
Output: [,[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]  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];
vector<int> out;
for (int j = 0; j < cnt; ++j) {
out.push_back(all[i + j]);
}
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;
}
};