剑指offer 03.数组中重复的数字 -- JAVA、python实现_java 给定一个长度为 n 的可能含有重复值的数组 nums,

题目

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 
1
2
3

限制：

2 <= n <= 100000
1

法1-- java

• 双重for循环 (n*n复杂度)

class Solution {
    public int findRepeatNumber(int[] nums) {
       
        for(int i= 0; i<nums.length; i++){
            for(int j = i+1; j < nums.length;j++){
                if(nums[i]==nums[j]){
                    return nums[i];                                  
                }
            }
        }
        return 1;
    }      
}
1
2
3
4
5
6
7
8
9
10
11
12
13

法2-- java、python

• 排序: 排序后的数组相同的元素必挨着,比较相邻元素是否相等就行 – O(n)

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);  // 这个排序方式要记住
        int num = 0; // 用户记录那个相同的数,用作最后的返回
        for(int i = 0; i < nums.length-1; i++){
            if(nums[i] == nums[i+1]){
                 num = nums[i];
                break;
            }     
        }
        return num;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                return nums[i]
1
2
3
4
5
6
7
8
9
10

法3 – python

• 利用set()的无重复元素的特性进行判断

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        temp_set = set()
        repeat = -1 # 重复的数
        for i in range(len(nums)):
            temp_set.add(nums[i]) # 第一个数存入集合
            if len(temp_set) < i+1:
                repeat = nums[i]
                break
        return repeat
1
2
3
4
5
6
7
8
9
10
11
12
13
14