題目
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]
解題思路
將nums[i]置換到其對(duì)應(yīng)的位置nums[nums[i]-1]上去崔步，比如對(duì)于沒有缺失項(xiàng)的正確的順序應(yīng)該是[1, 2, 3, 4, 5, 6, 7, 8]耘子，而我們現(xiàn)在卻是[4,3,2,7,8,2,3,1]浊伙，我們需要把數(shù)字移動(dòng)到正確的位置上去，比如第一個(gè)4就應(yīng)該和7先交換個(gè)位置痴怨，以此類推，最后得到的順序應(yīng)該是[1, 2, 3, 4, 3, 2, 7, 8]贴捡，我們最后在對(duì)應(yīng)位置檢驗(yàn)罚屋，如果nums[i]和i+1不等，那么我們將i+1存入結(jié)果res中即可
代碼
findDisappearedNumbers.go
package _448_Find_All_Numbers_Disappeared_in_an_Array
func FindDisappearedNumbers(nums []int) []int {
var ret []int
length := len(nums)
for i := 0; i < length; i++ {
if nums[i] != nums[nums[i] - 1] {
nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
i--
}
}
for i := 0; i < length; i++ {
if (i + 1) != nums[i] {
ret = append(ret, (i+1))
}
}
return ret
}
測(cè)試
findDisappearedNumbers_test.go
package _448_Find_All_Numbers_Disappeared_in_an_Array
import "testing"
func sliceEqual(want, ret []int) bool {
len1 := len(want)
len2 := len(ret)
if len1 != len2 {
return false
}
for i := 0; i < len1; i++ {
if want[i] != ret[i] {
return false
}
}
return true
}
func TestFindDisappearedNumbers(t *testing.T) {
input := []int{4,3,2,7,8,2,3,1}
want := []int{5,6}
ret := FindDisappearedNumbers(input)
ok := sliceEqual(want, ret)
if ok {
t.Logf("pass")
} else {
t.Errorf("fail, want %+v, get %+v", want, ret)
}
}
