leetcode:数组的重复数系列

题目一：Find All Duplicates in an Array

1、题目链接

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

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

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

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

Output:
[2,3]

2、Solution

题目的意思是，有一个 n 个数的数组，每个数的大小都在 [1,n] 之间，有的数出现了 2 次，有的数出现了 1 次。找到出现2次的数。

不用额外的空间，从数值大小的设定上来看，可以将数值和数组的索引关联起来，出现过的数，我们可以将对应索引上标记为负数，第二次出现时，如果索引上的值已被标记为负数，我们就知道它其实已经出现过一次啦～

go版的代码如下：

func findDuplicates(nums []int) []int {
    var res []int
    for i:=0;i<len(nums);i++{
        index := abs(nums[i])-1
        if nums[index] <0 {
            res =append(res,index+1)
        }
        nums[index] = -nums[index]
        
        
    }
    return res
}

func abs(num int) int{
    if num <0 {
        return -num
    }
    return num
}

题目二：Find All Numbers Disappeared in an Array

1、题目链接

leetcode No448: 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]

2、Solution

其实这个和题目一的思路几乎一模一样。

题目的意思是，有一个 n 个数的数组，每个数的大小都在 [1,n] 之间，有的数出现了 2 次，有的数出现了 1 次。找到没有出现过的数。

不用额外的空间，从数值大小的设定上来看，可以将数值和数组的索引关联起来，出现过的数，我们可以将对应索引上标记为负数，遍历一遍，不是负数的索引，就是一次都没有出现过的数啦～

golang的代码如下

func findDisappearedNumbers(nums []int) []int {
    var res []int
    for i:=0;i<len(nums);i++ {
        index := nums[i] -1 
        if(nums[i] < 0){
            index = nums[i]*(-1) - 1
        }
        if(nums[index] > 0){
            nums[index] = nums[index] * (-1)
        }
    }
    for i:=0;i<len(nums);i++{
        if(nums[i]>0){
            res = append(res,i+1)
        }
    }
    return res
}