Greedy Algorithm to Group the Numbers/Items Given the Group Size

  • 时间:2020-09-15 16:10:27
  • 分类:网络文摘
  • 阅读:105 次

There are n people whose IDs go from 0 to n – 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people’s IDs each group includes. You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.

Example 1:
Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation:
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 &lt= 500
1 <= groupSizes[i] <= n

Hints:
Put people’s IDs with same groupSize into buckets, then split each bucket into groups.
Greedy fill until you need a new group.

Group the Numbers by Greedy Algorithm

We can put the items in the same bucket, then apply a Greedy Algorithm to fill the groups (from large to small) until I need a new group. In C++, the std::map maintains the keys sorted in ascending order. We then can start from the last iterator (which is one position less than the end iterator), fill the groups (using the items in the buckets from largest to smallest order), until all elements are arranged.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ans;
        map<int, vector<int>> ids;
        for (int i = 0; i < groupSizes.size(); ++ i) {
            ids[groupSizes[i]].push_back(i);
        }
        int K = groupSizes.size();
        for (auto it = --ids.end(); K > 0; --K) {
            if (ans.empty() || (ans.back().size() >= it->first)) {
                ans.push_back({}); // need a new group
            }
            ans.back().push_back(it->second.back());
            it->second.pop_back(); // remove the ID from the candidate list
            if (it->second.empty()) {
                -- it; // next largest bucket
            }
        }
        return ans;
    }
};
class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ans;
        map<int, vector<int>> ids;
        for (int i = 0; i < groupSizes.size(); ++ i) {
            ids[groupSizes[i]].push_back(i);
        }
        int K = groupSizes.size();
        for (auto it = --ids.end(); K > 0; --K) {
            if (ans.empty() || (ans.back().size() >= it->first)) {
                ans.push_back({}); // need a new group
            }
            ans.back().push_back(it->second.back());
            it->second.pop_back(); // remove the ID from the candidate list
            if (it->second.empty()) {
                -- it; // next largest bucket
            }
        }
        return ans;
    }
};

Alternatively, we can iterate the map using the rbegin() and rend() which reverses the order (from right to left).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ans;
        map<int, vector<int>> ids;
        for (int i = 0; i < groupSizes.size(); ++ i) {
            ids[groupSizes[i]].push_back(i);
        }
        for (auto it = rbegin(ids); it != ids.rend(); ) {
            if (ans.empty() || (ans.back().size() >= it->first)) {
                ans.push_back({}); // need a new group
            }
            ans.back().push_back(it->second.back());
            it->second.pop_back();  // remove the ID from the candidate list
            if (it->second.empty()) {
                ++ it;
            }
        }
        return ans;
    }
};
class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ans;
        map<int, vector<int>> ids;
        for (int i = 0; i < groupSizes.size(); ++ i) {
            ids[groupSizes[i]].push_back(i);
        }
        for (auto it = rbegin(ids); it != ids.rend(); ) {
            if (ans.empty() || (ans.back().size() >= it->first)) {
                ans.push_back({}); // need a new group
            }
            ans.back().push_back(it->second.back());
            it->second.pop_back();  // remove the ID from the candidate list
            if (it->second.empty()) {
                ++ it;
            }
        }
        return ans;
    }
};

Both implementations require O(N) linear space and the time complexity is also O(N) where N is the number of the elements in the original list i.e. each number will be visited exactly twice.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
我爱秋天的凄凉  赛龙舟比赛  端午节划龙舟作文  十里粽飘香  以端午节为话题的作文  清明时节雨 作文  web网站安全防护解决办法大全  站长 不要忘了你的网站是做什么的  2020年 网站站长如何赚钱  seo是否真的已死?网站站长如何赚钱? 
评论列表
添加评论