diff options
author | Jack Sangdahl <[email protected]> | 2025-01-25 01:07:53 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-25 01:07:53 -0700 |
commit | 3c86d5ce6885144cf5db34e182066407191aea66 (patch) | |
tree | dc489050e17d7f9d4915fcb48eabbcc0ca8aa4a0 | |
parent | 74ac72e6213f2824302802013d14ab5bcf629fa4 (diff) | |
download | leetcode-3c86d5ce6885144cf5db34e182066407191aea66.tar.gz leetcode-3c86d5ce6885144cf5db34e182066407191aea66.zip |
2948. make lexicographically smallest array by swapping elements
-rw-r--r-- | make_lex_small_arr.c | 64 | ||||
-rw-r--r-- | make_lex_small_arr.py | 36 |
2 files changed, 100 insertions, 0 deletions
diff --git a/make_lex_small_arr.c b/make_lex_small_arr.c new file mode 100644 index 0000000..1633124 --- /dev/null +++ b/make_lex_small_arr.c @@ -0,0 +1,64 @@ +// 2948. Make Lexicographically Smallest Array by Swapping Elements +#include "leetcode.h" + +/* + * you are given a 0-indexed array of positive integers 'nums' and a positive + * integer 'limit'. in one operation, you can choose any two indices 'i' and 'j' + * and swap 'nums[i]' and 'nums[j]' if '|nums[i] - nums[j]| <= limit'. return + * the lexicographically smallest array that can be obtained by performingthe + * operation any number of times. + */ + +int cmp1(const void *a, const void *b) { + int *aa = (int *)a; + int *bb = (int *)b; + return aa[0] - bb[0]; +} + +int cmp2(const void *a, const void *b) { return *(int *)a - *(int *)b; } + +int *lexicographicallySmallestArray(int *nums, int numsSize, int limit, + int *returnSize) { + int *ans = (int *)malloc(numsSize * sizeof(int)); + *returnSize = numsSize; + int cpy[numsSize][2]; + for (int i = 0; i < numsSize; i++) { + cpy[i][0] = nums[i]; + cpy[i][1] = i; + } + qsort(cpy, numsSize, sizeof(cpy[0]), cmp1); + int indices[numsSize]; + for (int i = 0; i < numsSize;) { + int size = 0, prev = cpy[i][0]; + while (i < numsSize && cpy[i][0] <= (prev + limit)) { + indices[size++] = cpy[i][1]; + prev = cpy[i][0]; + i++; + } + qsort(indices, size, sizeof(int), cmp2); + for (int j = 0, k = i - size; j < size; j++, k++) + ans[indices[j]] = cpy[k][0]; + } + return ans; +} + +int main() { + int n1[] = {1, 5, 3, 9, 8}, rs1; + int n2[] = {1, 7, 6, 18, 2, 1}, rs2; + int n3[] = {1, 7, 28, 19, 10}, rs3; + int *lsa1 = lexicographicallySmallestArray(n1, ARRAY_SIZE(n1), 2, &rs1); + int *lsa2 = lexicographicallySmallestArray(n2, ARRAY_SIZE(n2), 3, &rs2); + int *lsa3 = lexicographicallySmallestArray(n3, ARRAY_SIZE(n3), 3, &rs3); + for (int i = 0; i < rs1; i++) + printf("%d ", lsa1[i]); // expect: 1 3 5 8 9 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", lsa2[i]); // expect: 1 6 7 18 1 2 + printf("\n"); + for (int i = 0; i < rs3; i++) + printf("%d ", lsa3[i]); // expect: 1 7 28 19 10 + printf("\n"); + free(lsa1); + free(lsa2); + free(lsa3); +} diff --git a/make_lex_small_arr.py b/make_lex_small_arr.py new file mode 100644 index 0000000..565469d --- /dev/null +++ b/make_lex_small_arr.py @@ -0,0 +1,36 @@ +# 2948. Make Lexicographically Smallest Array by Swapping Elements + +""" +you are given a 0-indexed array of positive integers 'nums' and a positive +integer 'limit'. in one operation, you can choose any two indices 'i' and 'j' +and swap 'nums[i]' and 'nums[j]' if '|nums[i] - nums[j]| <= limit'. return +the lexicographically smallest array that can be obtained by performingthe +operation any number of times. +""" + + +class Solution(object): + def lexicographicallySmallestArray(self, nums, limit): + """ + :type nums: List[int] + :type limit: int + :rtype: List[int] + """ + n, indices = len(nums), [] + cpy, ans = sorted([(nums[i], i) for i in range(n)]), [0] * n + for i in range(n): + if i == 0 or cpy[i][0] - cpy[i - 1][0] > limit: + indices.append([]) + indices[-1].append(cpy[i][1]) + for i in indices: + curr = sorted(i) + for j in range(len(i)): + ans[curr[j]] = nums[i[j]] + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.lexicographicallySmallestArray(nums=[1, 5, 3, 9, 8], limit=2)) + print(obj.lexicographicallySmallestArray(nums=[1, 7, 6, 18, 2, 1], limit=3)) + print(obj.lexicographicallySmallestArray(nums=[1, 7, 28, 19, 10], limit=3)) |