一、剑指 Offer 03. 数组中重复的数字

要求：找出数组中重复的数字。

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

解法：

暴力遍历，用hashset存储（不能用hashmap，会超时）。遇到重复的就return。检查是否存在这个元素，用contains方法。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int findRepeatNumber(int[] nums) {
        HashSet<Integer> numSet = new HashSet<>();

        for(int num:nums){
            if(numSet.contains(num)){
                return num;
            }
            numSet.add(num);
        }
        return -1;
    }
}

二、剑指 Offer 53 - I. 在排序数组中查找数字 I

要求：统计一个数字在排序数组中出现的次数。

思路：就是先用二分查找定位到要查找的目标数字，再定义一个左索引和右索引，左移和右移指针，分别遍历定位好的目标数字的左边和右边的数字，如果这两个索引指向的值和目标数字相同，则count++，否则就结束左移和右移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public static int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int count = 0;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (nums[mid] > target) {
                end = mid - 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                count++;
                int left = mid - 1;
                int right = mid + 1;
                while (left >= 0) {
                    if(nums[left]==nums[mid]){
                        count++;
                        left-=1;
                    }else{
                        break;
                    }

                }
                while (right <= nums.length-1) {
                    if(nums[right]==nums[mid]){
                        count++;
                        right+=1;
                    }else{
                        break;
                    }

                }
                break;
            }
        }
        return count;
    }
}

三、剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

思路：

利用二分查找

  1. 如果数组中间的数nums[mid]正好等于mid，说明这个mid之前的所有数都是正常的，并无缺失，继续在后半段二分查找。
  2. 如果数组中间的数nums[mid]大于mid，说明这个mid之前的数字有缺失。开始查找这个数的左侧数字是否正常。
    1. 检查这个mid的左边，如果mid的左边left有值，就看这个值是不是正常的，如果正常，那说明缺失的就是left和mid之间的值。
    2. 如果mid的左边left有值，且这个值也不正常，继续在前半段二分查找。
    3. 如果找到最后，发现mid已经是第一个值，left没有值了，mid的值依然不正常，那就说明缺失的就在第一个值，也就是mid之前，也就是数字0。
  3. 如果找到最后，发现已经找到最后一个mid了，但是这个mid之前的所有数仍然都是正常的，并无缺失，说明缺失的肯定就是最末尾的值了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public static int missingNumber(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        int mid = (start + end)/2;
        while(start<=end){
            mid = (start + end)/2;
            if(nums[mid] == mid){
                start = mid + 1;
            }
            if(nums[mid] > mid){
                int left = mid -1;
                if(left>=0){
                    if(nums[left] == left){
                        return left + 1;
                    }
                }else{
                    return 0;
                }
                end = mid - 1;
            }
        }
        return mid + 1;
    }
}

标准答案：

1
2
3
4
5
6
7
8
9
public int missingNumber(int[] nums) {
    int i = 0, j = nums.length - 1;
    while(i <= j) {
        int m = (i + j) / 2;
        if(nums[m] == m) i = m + 1;
        else j = m - 1;
    }
    return i;
}