Question

2610. Convert an Array Into a 2D Array With Conditions

中文文档

Description

You are given an integer array nums. You need to create a 2D array from nums satisfying the following conditions:

• The 2D array should contain only the elements of the array nums.
• Each row in the 2D array contains distinct integers.
• The number of rows in the 2D array should be minimal.

Return _the resulting array_. If there are multiple answers, return any of them.

Note that the 2D array can have a different number of elements on each row.

 

Example 1:

Input: nums = [1,3,4,1,2,3,1]
Output: [[1,3,4,2],[1,3],[1]]
Explanation: We can create a 2D array that contains the following rows:
- 1,3,4,2
- 1,3
- 1
All elements of nums were used, and each row of the 2D array contains distinct integers, so it is a valid answer.
It can be shown that we cannot have less than 3 rows in a valid array.

Example 2:

Input: nums = [1,2,3,4]
Output: [[4,3,2,1]]
Explanation: All elements of the array are distinct, so we can keep all of them in the first row of the 2D array.

 

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= nums.length

Solutions

Solution 1: Array or Hash Table

We use an array or hash table $cnt$ to count the number of occurrences of each element in the array $nums$.

Then we traverse the $cnt$ array, add $x$ to the $0$th row, the $1$st row, the $2$nd row, …, the ($cnt[x]-1$)th row of the answer list.

Finally, return the answer list.

The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the length of the array $nums$.

class Solution:
  def findMatrix(self, nums: List[int]) -> List[List[int]]:
    cnt = Counter(nums)
    ans = []
    for x, v in cnt.items():
      for i in range(v):
        if len(ans) <= i:
          ans.append([])
        ans[i].append(x)
    return ans

class Solution {
  public List<List<Integer>> findMatrix(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    int n = nums.length;
    int[] cnt = new int[n + 1];
    for (int x : nums) {
      ++cnt[x];
    }
    for (int x = 1; x <= n; ++x) {
      int v = cnt[x];
      for (int j = 0; j < v; ++j) {
        if (ans.size() <= j) {
          ans.add(new ArrayList<>());
        }
        ans.get(j).add(x);
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<vector<int>> findMatrix(vector<int>& nums) {
    vector<vector<int>> ans;
    int n = nums.size();
    vector<int> cnt(n + 1);
    for (int& x : nums) {
      ++cnt[x];
    }
    for (int x = 1; x <= n; ++x) {
      int v = cnt[x];
      for (int j = 0; j < v; ++j) {
        if (ans.size() <= j) {
          ans.push_back({});
        }
        ans[j].push_back(x);
      }
    }
    return ans;
  }
};

func findMatrix(nums []int) (ans [][]int) {
  n := len(nums)
  cnt := make([]int, n+1)
  for _, x := range nums {
    cnt[x]++
  }
  for x, v := range cnt {
    for j := 0; j < v; j++ {
      if len(ans) <= j {
        ans = append(ans, []int{})
      }
      ans[j] = append(ans[j], x)
    }
  }
  return
}

function findMatrix(nums: number[]): number[][] {
  const ans: number[][] = [];
  const n = nums.length;
  const cnt: number[] = new Array(n + 1).fill(0);
  for (const x of nums) {
    ++cnt[x];
  }
  for (let x = 1; x <= n; ++x) {
    for (let j = 0; j < cnt[x]; ++j) {
      if (ans.length <= j) {
        ans.push([]);
      }
      ans[j].push(x);
    }
  }
  return ans;
}