Skip to content

LeetCode: 1282-Group the People Given the Group Size They Belong To 解題紀錄

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

You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.

Return a list of groups such that each person i is in a group of size 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

簡單來說，題目給定的 groupSizes 裡面的每一個值，代表著『應該被歸類到多少數量的陣列中』，而在歸類到的陣列中，應該用索引（index）儲存著。

解題思路

這題我是直接暴力法，用 hash 來讓『應該建立的陣列長度』對應到『陣列群集』中，然後在讀取到輸入陣列的數值時，直接匹配到對應長度的陣列中。

比方說我的第一個值是 3，我就建立一個 3 => arr(arr()) 的對應，然後把 index=0 放在裡頭。依此類推，如果陣列即將大於 3 ，就再新增另外一個陣列放在數值 3 對應的 mapping 表中。


C++ 範例程式碼

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        // Init
        int maxSize = 0;
        vector<vector<int>> results;
        unordered_map<int, vector<vector<int>>> idx2groupArr;

        // Split
        for (int i=0; i<groupSizes.size(); ++i) {
            int currSize = groupSizes[i];
            maxSize = max(maxSize, currSize);
            bool fit = false;

            for (vector<int>& arr: idx2groupArr[currSize]) {
                if (arr.size() < currSize) {
                    arr.emplace_back(i);
                    fit = true;
                    break;
                }
            }

            if (!fit) {
                vector<int> newArr({i});
                idx2groupArr[currSize].emplace_back(newArr);
            }
        }

        // Format
        for (int size=1; size<=maxSize; ++size) {
            for (vector<int>& arr: idx2groupArr[size]) {
                results.emplace_back(arr);
            }
        }

        return results;
    }
};



Python 範例程式碼

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        # Init
        max_size = 0
        results = []
        idx2arr = {}

        # Split
        for i in range(len(groupSizes)):
            curr_size = groupSizes[i]
            max_size = max(max_size, curr_size)
            fit = False

            if curr_size not in idx2arr:
                idx2arr[curr_size] = [[i]]
                continue
            
            for arr in idx2arr[curr_size]:
                if len(arr) < curr_size:
                    arr.append(i)
                    fit = True
                    break

            if not fit:
                idx2arr[curr_size].append([i])

        # Format
        for size in range(1, max_size+1):
            if size not in idx2arr:
                continue
                
            for arr in idx2arr[size]:
                results.append(arr)

        return results

References

Read More

Tags:

Leave a Reply