leetcode:数组的重复数系列

air03_30 · · 572 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

题目一: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
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:air03_30

查看原文:leetcode:数组的重复数系列

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

572 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传