未分類

Find All Numbers Disappeared in an Array

Array, Go, LeetCode

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.

For Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
提示 解題應用
Array Slice

Default:

1
2
3
func findDisappearedNumbers(nums []int) []int {
}

解答思路:

因為想不透解法，看了別人討論的解法，雖然這種小技巧確實可以達到目標，不過一般也不會對資料做修改，寧可在空間上做些花費來記錄，而這招時間上會花費n+n的複雜度，首先先用一回圈遍歷將拿到的值-1當作index，並將原本在陣列上該index的值改為負數，如此一來在全數遍歷完成之後，陣列上沒有變為負數的值，其index在+1就會是陣列缺少的值，所以再次進行遍歷將那些值放入結果即可回傳。

程式碼解說:

一開始先以迴圈進行遍歷，並將拿到的值-1當作index，再把原本在陣列上該index的值改為負數，不過改回負數時再回到一開始要當作index的狀況時就會有問題，所以迴圈遍歷時，取出元素後要先確保其為正數，如果是負數就要先轉為正數，這邊我們用自己刻的abs來簡單判斷，如果index的其值尚為正數就改為負數，最後再次利用迴圈將所有不為負數的其index+1放入結果之中回傳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func findDisappearedNumbers(nums []int) []int {
    var result []int
    var target int
    for _,v := range nums {
        v = abs(v)
        target = nums[v-1]
        if target > 0 {
            nums[v-1] = - target
        }
    }
    for i,v := range nums {
        if v > 0 {
            result = append(result,i+1)
        }
    }
    return result
}

非常單純判斷並將負數轉為正值的function，如此一來就不需要載入整個math的library

1
2
3
4
5
6
func abs(num int) int {
    if num < 0 {
        return -num
    }
    return num
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func findDisappearedNumbers(nums []int) []int {
    var result []int
    var target int
    for _,v := range nums {
        v = abs(v)
        target = nums[v-1]
        if target > 0 {
            nums[v-1] = - target
        }
    }
    for i,v := range nums {
        if v > 0 {
            result = append(result,i+1)
        }
    }
    return result
}
func abs(num int) int {
    if num < 0 {
        return -num
    }
    return num
}

總結:

一陣列若其長度為n，則該儲存元素需為1~n，若要找出缺少的元素且不能使用額外空間，首先先用一回圈遍歷將拿到的值-1當作index，並將原本在陣列上該index的值改為負數，在全數遍歷完成之後，陣列上沒有變為負數的值，其index在+1就會是陣列缺少的值。

分享到