力扣—2024/4/18—从双倍数组中还原原数组

本文主要是介绍力扣—2024/4/18—从双倍数组中还原原数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码实现：

快排 + 哈希表 ——超时

/*** Note: The returned array must be malloced, assume caller calls free().*/
void swap(int *m, int *n) {int temp = *m;*m = *n;*n = temp;
}// 快排
void sort(int *a, int l, int r) { // 左闭右开if (r - l <= 2) {if (r - l <= 1) {return;} if (a[l] > a[r - 1]) {swap(&a[l], &a[r - 1]);}return;}int i = l, j = r - 1;int pivot = a[i];while (i < j) {while (i < j && a[j] >= pivot) {j--;}if (i < j) {a[i] = a[j];i++;}while (i < j && a[i] <= pivot) {i++;}if (i < j) {a[j] = a[i];j--;}}a[i] = pivot;sort(a, l, i);sort(a, i + 1, r);
}int* findOriginalArray(int *changed, int changedSize, int *returnSize) {*returnSize = 0;if (changedSize == 0 || changedSize % 2) {return NULL;}int *res = malloc(sizeof(int) * changedSize / 2);sort(changed, 0, changedSize);int hash[100001] = {0};for (int i = 0; i < changedSize; i++) {hash[changed[i]]++;}for (int i = 0; i < changedSize; i++) {if (hash[changed[i]] == 0) {continue;}if (changed[i] == 0 && hash[0] < 2) { // 特别处理0的情况*returnSize = 0;return NULL;}if (hash[changed[i] * 2] == 0) {*returnSize = 0;return res;}res[(*returnSize)++] = changed[i];hash[changed[i]]--;hash[changed[i] * 2]--;}return res;
}

这篇关于力扣—2024/4/18—从双倍数组中还原原数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---