Sponsored
Sponsored
The main idea is to utilize a hash map (or dictionary) to count the occurrences of each element in the input array. This helps us determine how many rows we will need based on the maximum frequency of any element.
Then, we iteratively fill the 2D array by distributing each unique element to different rows, ensuring each row contains distinct integers.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), because of the storage needed for the count map and result array.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5void convertArray(int* nums, int numsSize) {
6 int count[201] = {0};
7 for (int i = 0; i < numsSize; ++i) {
8 count[nums[i]]++;
9 }
10 int max_frequency = 0;
11 for (int i = 1; i <= numsSize; i++) {
12 if (count[i] > max_frequency) {
13 max_frequency = count[i];
14 }
15 }
16 int** result = (int**)malloc(max_frequency * sizeof(int*));
17 for (int i = 0; i < max_frequency; i++) {
18 result[i] = (int*)malloc(numsSize * sizeof(int));
19 memset(result[i], 0, numsSize * sizeof(int));
20 }
21 int* idx_array = (int*)calloc(max_frequency, sizeof(int));
22 int index = 0;
23 for (int i = 1; i <= numsSize; i++) {
24 for (int j = 0; j < count[i]; ++j) {
25 result[index][idx_array[index]++] = i;
26 index = (index + 1) % max_frequency;
27 }
28 }
29 for (int i = 0; i < max_frequency; i++) {
30 for (int j = 0; j < idx_array[i]; j++) {
31 printf("%d ", result[i][j]);
32 }
33 printf("\n");
34 }
35 for (int i = 0; i < max_frequency; i++) {
36 free(result[i]);
37 }
38 free(result);
39 free(idx_array);
40}
41
42// Example usage
43int main() {
44 int nums[] = {1, 3, 4, 1, 2, 3, 1};
45 int numsSize = sizeof(nums) / sizeof(nums[0]);
46 convertArray(nums, numsSize);
47 return 0;
48}In C, an array is used to count the frequencies of elements. The maximum frequency determines the number of necessary rows. A round-robin approach is used to distribute the elements across the result rows, while dynamically managing memory for accessibility.
This approach first sorts the array to easily group identical elements. Starting from the least element, it places each new occurrence in different rows to ensure minimal rows while adhering to the distinct integer rule per row.
Time Complexity: O(n log n), because of sorting.
Space Complexity: O(n), for storing the result array.
1#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;
vector<vector<int>> convertArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for (auto num : nums) {
bool placed = false;
for (auto& row : result) {
unordered_set<int> rowSet(row.begin(), row.end());
if (!rowSet.count(num)) {
row.push_back(num);
placed = true;
break;
}
}
if (!placed) {
result.push_back(vector<int>{num});
}
}
return result;
}
// Example usage
int main() {
vector<int> nums = {1, 3, 4, 1, 2, 3, 1};
vector<vector<int>> result = convertArray(nums);
for (const auto& row : result) {
for (int num : row) {
cout << num << " ";
}
cout << endl;
}
return 0;
}In C++, the array is sorted first. For each number, it checks its compatibility with existing rows using unordered_sets and places it accordingly, creating a new row if necessary.