力扣448. 找到所有數組中消失的數字

• 2021 年 2 月 13 日
• 筆記
• C語言, 力扣, 力扣刷題, 演算法

題目

[傳送門]

給定一個範圍在 1 ≤ a[i] ≤ n ( n = 數組大小 ) 的 整型數組，數組中的元素一些出現了兩次，另一些只出現一次。
找到所有在 [1, n] 範圍之間沒有出現在數組中的數字。
您能在不使用額外空間且時間複雜度為O(n)的情況下完成這個任務嗎? 你可以假定返回的數組不算在額外空間內。

示例:

輸入:
[4,3,2,7,8,2,3,1]

輸出:

[5,6]

來源：力扣（LeetCode）

解題

模板

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){

}

分析

題目要求是求出對於數組內n長度的數組，本因保持數組內有1-n的自然數，如果有符合條件的自然數沒有包括在內，就返回由該類型自然數組成的數組。

邏輯分析

條件可得，元素都是有範圍的處於1~n之間，所以我們可以建立一個新數組，下標+1來對應原數組內的範圍，新數組設為new就是，new[0]代表的就是原數組中1出現的次數。

依據最後返回的new數組中是0的就是沒出現的，而對應的下標+1就是沒出現的數字；
基於此基礎之上對於部分邏輯更改，因為對於其中的過程最好能不適用新建數組就不新建，這樣能更好的避免浪費資源。
參考程式碼如下：【傳送門】

程式碼：

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
   for (int i = 0; i < numsSize; i++) {
       int x = (nums[i] - 1) % numsSize;
       nums[x] += numsSize;
   }
   int* ret = malloc(sizeof(int) * numsSize);
   *returnSize = 0;
   for (int i = 0; i < numsSize; i++) {
       if (nums[i] <= numsSize) {
           ret[(*returnSize)++] = i + 1;
       }
   }
   return ret;
}