【Golang】LeetCode442Find All Duplicates in an Array
给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?
示例:
输入:[4,3,2,7,8,2,3,1]输出:[2,3]
题意:关键就是把数组中的元素当成是索引来看就行。如果索引处的数字出现过一次,就给-1,因为只会出现两次,如果第二次再出现,那么对应位置的值就会是小于0的,直接加到结果集中就行。一开始我还想着出现过一次-1,再出现一次再*-1,这样最后再遍历一次找到小于0的即可,但是发现有些问题,有些数字没出现过会被误杀。
O(N)时间,O(1)空间
func findDuplicates(nums []int) []int { result := make([]int, 0) for _, v := range nums { v = int(math.Abs(float64(v))) if nums[v-1] > 0 { nums[v-1] = nums[v-1] * -1 } else { result = append(result, v) } } return result}
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。