題目

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

解答

C#

public class Solution {
    public IList<int> FindDisappearedNumbers(int[] nums) {
        List<int> result = new List<int>();
        int numsLength = nums.Length;

        for (int i = 0; i < numsLength; i++)
        {
            int index = Math.Abs(nums[i]) - 1;
            if (nums[index] > 0)
            {
                nums[index] = -nums[index];
            }
        }

        for (int i = 0; i < numsLength; i++)
        {
            if (nums[i] > 0)
            {
                result.Add(i + 1);
            }
        }

        return result;
    }
}

結果

Runtime: 308 ms, faster than 98.68% of C# online submissions.

Memory Usage: 42.6 MB, less than 50.0% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(n)

為什麼我要這樣做？

這題主要是在說，我給你一個 size = n 的 array
裡面應該要有 1 ~ n 的數字，不一定是排序過的 array
請幫我找出漏掉的數字並回傳 List<int>

一開始我本來用 Dictionary 去紀錄消失的數字，但效果不彰
所以改用 nums array 本身去紀錄，這樣效能也比較好

1. 第一個 for 迴圈
   • 找出每個數字在 array 排序後的 index
     • 例如 {3, 2, 1} sorted -> {1, 2, 3}
     • 3 的 index = 0 ... etc
   • 將 array 裡，屬於那個 index 的數字，標記成負數 ，nums[index] = -nums[index]
     • 也因為之後的數字有可能被標記成負數，所以才需要用到 Math.Abs 取 絕對值，再去找 index
2. 第二個 for 迴圈
   • 沒有被標記成負數的 index，就是消失 的數字，所以將index+1 Add 到 result 即可
     • 例如 {3, 2, 3} 最後會被標記成 {3, -2, -3}
       • -2 代表有找到 2 (index:1) 這個數字
       • -3 代表有找到 3 (index:2) 這個數字
       • 2 則代表沒有找到 1 (index:0) 這個數字
     • 回傳 index+1 則是 array index 起始為 0，陣列數字起始為 1

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉