算法:找出数组中的重复数字

2020-12-15 22:21:04 编辑 1 阅读量:421

题目如下：

```
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]
```

观察题目意思为元素值不会超出数组长度，所以可以利用数组本身的元素作为判断符。判断符有两种做法：1、该位置1；2、改位符号取反。因为这里不能改变元素的绝对值（会改变后续判断），所以采用2方法。解法有3中，具体如下：

```python
class Solution(object):
    def find_duplicates_first(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        statuslist = {}
        result = []
        for i, x in enumerate(nums):
            if statuslist.get(x, 0) == 1:
                result.append(x)
            else:
                statuslist[x] = 1
        return result

def find_duplicates_low_speed(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        status = 0
        result = []
        for x in nums:
            tmp = 1 << x
            if tmp & status != 0:
                result.append(x)
            else:
                status = status | tmp
        return result
        
    def find_duplicates(self, nums):
        res = []
        for x in nums:
            if nums[abs(x)-1] < 0:
                res.append(abs(x))
            else:
                nums[abs(x)-1] *= -1
            print nums
        return res

solution = Solution()
print solution.find_duplicates([4,3,2,7,8,2,3,1])

print solution.find_duplicates([])
print solution.find_duplicates([1])
print solution.find_duplicates([1,1])
```

算法:找出数组中的重复数字

附件: