diff options
author | Jack Sangdahl <[email protected]> | 2025-06-17 23:46:46 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-17 23:46:46 -0600 |
commit | f2349693f5c352357a135454fde298f109b2198a (patch) | |
tree | 877906bd9e09f2787dc1eb749f460d882d95b247 | |
parent | 403a31eb22ad406e0d49a72b867a057121828cc2 (diff) | |
download | leetcode-f2349693f5c352357a135454fde298f109b2198a.tar.gz leetcode-f2349693f5c352357a135454fde298f109b2198a.zip |
2966. divide array into arrays with max difference
-rw-r--r-- | divide_array_max_diff.c | 69 | ||||
-rw-r--r-- | divide_array_max_diff.py | 17 |
2 files changed, 63 insertions, 23 deletions
diff --git a/divide_array_max_diff.c b/divide_array_max_diff.c index 72e8648..8c510b3 100644 --- a/divide_array_max_diff.c +++ b/divide_array_max_diff.c @@ -11,25 +11,66 @@ * return any of them */ -int cmp(const void *a, const void *b) { return (*(int *)a) - (*(int *)b); } +int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } int **divideArray(int *nums, int numsSize, int k, int *returnSize, int **returnColumnSizes) { - int num_arr = numsSize / 3; - int **ans = (int **)calloc(num_arr, sizeof(int *)); - *returnColumnSizes = (int *)calloc(num_arr, sizeof(int)); - *returnSize = 0; qsort(nums, numsSize, sizeof(int), cmp); - for (int i = 0; i < num_arr; i++) { - ans[i] = (int *)calloc(3, sizeof(int)); - (*returnColumnSizes)[i] = 3; - for (int j = 0; j < 3; j++) { - int idx = i * 3 + j; - if (j && nums[idx] - nums[i * 3] > k) - return ans; - ans[i][j] = nums[idx]; + int **ans = (int **)malloc((numsSize / 3) * sizeof(int *)), rs = 0; + for (int i = 2; i < numsSize; i += 3) { + if (nums[i] - nums[i - 2] > k) { + *returnSize = 0; + return NULL; } + ans[rs] = (int *)malloc(3 * sizeof(int)); + ans[rs][0] = nums[i - 2]; + ans[rs][1] = nums[i - 1]; + ans[rs][2] = nums[i]; + rs++; } - *returnSize = num_arr; + *returnSize = rs; + *returnColumnSizes = (int *)malloc(rs * sizeof(int)); + for (int i = 0; i < rs; i++) + (*returnColumnSizes)[i] = 3; return ans; } + +int main() { + int n1[] = {1, 3, 4, 8, 7, 9, 3, 5, 1}, rs1, *rcs1; + int n2[] = {2, 4, 2, 2, 5, 2}, rs2, *rcs2; + int n3[] = {4, 2, 9, 8, 2, 12, 7, 12, 10, 5, 8, 5, 5, 7, 9, 2, 5, 11}, rs3, + *rcs3; + int **da1 = divideArray(n1, ARRAY_SIZE(n1), 2, &rs1, &rcs1); + int **da2 = divideArray(n2, ARRAY_SIZE(n2), 2, &rs2, &rcs2); + int **da3 = divideArray(n3, ARRAY_SIZE(n3), 14, &rs3, &rcs3); + for (int i = 0; i < rs1; i++) { + for (int j = 0; j < rcs1[i]; j++) + printf("%d ", da1[i][j]); // expect: [[1,1,3],[3,4,5],[7,8,9]] + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs2; i++) { + for (int j = 0; j < rcs2[i]; j++) + printf("%d ", da2[i][j]); // expect: null + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs3; i++) { + for (int j = 0; j < rcs3[i]; j++) + printf( + "%d ", + da3[i][j]); // expect: + // [[2,2,12],[4,8,5],[5,9,7],[7,8,5],[5,9,10],[11,12,2]] + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs1; i++) + free(da1[i]), free(rcs1); + free(da1); + for (int i = 0; i < rs2; i++) + free(da2[i]), free(rcs2); + free(da1); + for (int i = 0; i < rs3; i++) + free(da3[i]), free(rcs3); + free(da1); +} diff --git a/divide_array_max_diff.py b/divide_array_max_diff.py index 41a2a22..3bdf682 100644 --- a/divide_array_max_diff.py +++ b/divide_array_max_diff.py @@ -18,18 +18,12 @@ class Solution(object): :type k: int :rtype: List[List[int]] """ - size = len(nums) - if size % 3 != 0: - return [] nums.sort() ans = [] - group_idx = 0 - for i in range(0, size, 3): - if i + 2 < size and nums[i + 2] - nums[i] <= k: - ans.append([nums[i], nums[i + 1], nums[i + 2]]) - group_idx += 1 - else: + for i in range(2, len(nums), 3): + if nums[i] - nums[i - 2] > k: return [] + ans.append([nums[i - 2], nums[i - 1], nums[i]]) return ans @@ -37,3 +31,8 @@ if __name__ == "__main__": obj = Solution() print(obj.divideArray(nums=[1, 3, 4, 8, 7, 9, 3, 5, 1], k=2)) print(obj.divideArray(nums=[1, 3, 3, 2, 7, 3], k=3)) + print( + obj.divideArray( + nums=[4, 2, 9, 8, 2, 12, 7, 12, 10, 5, 8, 5, 5, 7, 9, 2, 5, 11], k=14 + ) + ) |