# 448. Find All Numbers Disappeared in an Array

題目：<https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/>

解法：把整數(1, n)對應原本陣列nums的index(0, n-1)，將出現過的數字對應整列位置用0標記，採用類似遞迴的方式反覆迭代後，沒有標記為0的位置即代表消失的數字
Time Complexity : O(n)
Space Complexity : O(1)

Python3：

class Solution:
    def findDisappearedNumbers(self, nums: list[int]) -> list[int]:
        n = len(nums)
        i = 0
        while i < n:
            j = nums[i] - 1
            while nums[j] != 0:
                nums[j], j = 0, nums[j] - 1
            i += 1
            while i < n and nums[i] == 0:
                i += 1
        return [i + 1 for i in range(n) if nums[i] != 0]

if __name__ == '__main__':
    nums = [4, 3, 2, 7, 8, 2, 3, 1]

    ans = Solution().findDisappearedNumbers(nums)

    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
    int i = 0;
    while (i < numsSize) {
        int j = nums[i] - 1;
        while (nums[j] != 0) {
            int tmp = j;
            j = nums[j] - 1;
            nums[tmp] = 0;
        }
        i++;
        while (i < numsSize && nums[i] == 0)
            i++;
    }
    *returnSize = 0;
    for (int i= 0; i < numsSize; i++) {
        if (nums[i] != 0)
            nums[(*returnSize)++] = i + 1;
    }
    return nums;
}

int main()
{
    int nums[] = {4, 3, 2, 7, 8, 2, 3, 1};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int returnSize;
    
    int* ans = findDisappearedNumbers(nums, numsSize, &returnSize);
    
    for (int i = 0; i < returnSize; i++)
        printf("%d ", ans[i]);
    printf("\n");
    
    
    return 0;
}

###### tags: `leetcode` `array`