diff options
author | Jack Sangdahl <[email protected]> | 2024-09-15 13:40:38 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-15 13:40:38 -0600 |
commit | 8850c53cf77d11bc3a4baf25eaf4a8292511c35b (patch) | |
tree | c59c1778fec6fd791b63f4ffec49c7b5b56dd3f8 | |
parent | ccbfd54d4a6c45f92f556f4aab02b099703d197d (diff) | |
download | leetcode-8850c53cf77d11bc3a4baf25eaf4a8292511c35b.tar.gz leetcode-8850c53cf77d11bc3a4baf25eaf4a8292511c35b.zip |
1054. distant barcodes
-rw-r--r-- | distant_barcodes.c | 46 | ||||
-rw-r--r-- | distant_barcodes.py | 29 |
2 files changed, 75 insertions, 0 deletions
diff --git a/distant_barcodes.c b/distant_barcodes.c new file mode 100644 index 0000000..f68da8d --- /dev/null +++ b/distant_barcodes.c @@ -0,0 +1,46 @@ +// 1054. Distant Barcodes +#include "leetcode.h" + +/* + * in a warehouse, there is a row of barcodes where the i'th barcode is + * 'barcodes[i]'. rearrange the barcodes so that no two adjacent barcodes are + * equal. you may return any answer, and it is guaranteed that an answer exists + */ + +int cmp(const void *a, const void *b) { return (*(int *)b - *(int *)a); } + +int *rearrangeBarcodes(int *barcodes, int barcodesSize, int *returnSize) { + int *cnt = (int *)calloc(1e4 + 1, sizeof(int)), max_val = 0; + for (int i = 0; i < barcodesSize; i++) { + cnt[barcodes[i]] = (cnt[barcodes[i]] + 0x10000) | barcodes[i]; + max_val = fmax(max_val, barcodes[i]); + } + qsort(cnt, max_val + 1, sizeof(int), cmp); + int idx = 0, b_idx = 0; + while (cnt[idx]) { + int curr = cnt[idx] & 0xFFFF; + cnt[idx] >>= 16; + for (int i = 0; i < cnt[idx]; i++) { + barcodes[b_idx] = curr; + b_idx += 2; + if (b_idx >= barcodesSize) + b_idx = 1; + } + cnt[idx++] = 0; + } + *returnSize = barcodesSize; + return barcodes; +} + +int main() { + int b1[] = {1, 1, 1, 2, 2, 2}, b2[] = {1, 1, 1, 1, 2, 2, 3, 3}, rs1, rs2; + int *rb1 = rearrangeBarcodes(b1, ARRAY_SIZE(b1), &rs1); + int *rb2 = rearrangeBarcodes(b2, ARRAY_SIZE(b2), &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", rb1[i]); // expect: 2,1,2,1,2,1 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", rb2[i]); // expect: 1,3,1,3,1,2,1,2 + printf("\n"); + free(rb1), free(rb2); +} diff --git a/distant_barcodes.py b/distant_barcodes.py new file mode 100644 index 0000000..e0fbb74 --- /dev/null +++ b/distant_barcodes.py @@ -0,0 +1,29 @@ +# 1054. Distant Barcodes +from collections import Counter + +""" +in a warehouse, there is a row of barcodes where the i'th barcode is +'barcodes[i]'. rearrange the barcodes so that no two adjacent barcodes are +equal. you may return any answer, and it is guaranteed that an answer exists +""" + + +class Solution(object): + def rearrangeBarcodes(self, barcodes): + """ + :type barcodes: List[int] + :rtype: List[int] + """ + cnt = Counter(barcodes) + barcodes.sort(key=lambda b: (cnt[b], b)) + barcodes[1::2], barcodes[::2] = ( + barcodes[0 : len(barcodes) / 2], + barcodes[len(barcodes) / 2 :], + ) + return barcodes + + +if __name__ == "__main__": + obj = Solution() + print(obj.rearrangeBarcodes(barcodes=[1, 1, 1, 2, 2, 2])) + print(obj.rearrangeBarcodes(barcodes=[1, 1, 1, 1, 2, 2, 3, 3])) |