[数据结构与算法]LeetCode.剑指Offer 03.数组中重复的数字

题目

解法一

因为题目只要求返回其中一个重复元素，所以可以直接使用一层循环来解决问题。在循环前，可以先将数组进行排列，排列后重复元素必然相邻，用下标和下标+1表示两个元素，进行比对，若相等，则为重复元素，可以直接跳出循环进行输出。如下图：

代码：

class Solution {
    public int findRepeatNumber(int[] nums) {
       Arrays.sort(nums);
       //0 1 2 2 3 3 5
        //   i i+1
        int r = 0;
        for(int i = 0;i <nums.length-1;i++){
            if(nums[i]==nums[i+1]){
                r = nums[i+1];
                break;
            }
        }  
        return r;
    }
}

解法二

因为是寻找重复元素，可以利用HashSet的add()方法来解决问题。

• set.add()：用来向 Set 集合添加对象，返回值为boolean。如果 Set 集合中不包含要添加的对象，则添加对象并返回true，否则返回 false。

代码：

class Solution {
    public int findRepeatNumber(int[] nums) {
        int result = 0;
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i<nums.length;i++){
        	//如果有重复元素（false）则将该值给result
            if(!set.add(nums[i])){
                result = nums[i];
            }
        }
        return result;
    }
}