Ming
0%

Leetcode-34

Posted on Edited on In

题目

结果

二分查找 2.0

Snipaste_2020-12-01_10-37-02.png

代码

一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[2];
        boolean flag = false;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                ans[0] = i;
                flag = true;
                break;
            }
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == target) {
                ans[1] = i;
                break;
            }
        }
        if (!flag) {
            ans[0] = -1;
            ans[1] = -1;
        }
        return ans;
    }
}

二分查找

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 特殊情况特殊考虑
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int index = search(nums, target, 0, nums.length - 1);
        if (index == -1) {
            return new int[]{-1, -1};
        }
        return lookAround(nums, index);
    }

    // 找到和target相等的一个元素的下标
    public int search(int[] nums, int target, int begin, int end) {
        // 只剩一个数的时候结束递归
        if (begin == end) {
            return nums[begin] == target ? begin : -1;
        }
        int middle = (begin + end) / 2;
        // 找到答案时结束递归
        if (nums[middle] == target) {
            return middle;
        } else if (nums[middle] < target) {
            if (middle == end) {
                return search(nums, target, middle, end);
            } else {
                return search(nums, target, middle + 1, end);
            }
        } else {
            if (middle == begin) {
                return search(nums, target, begin, middle);
            } else {
                return search(nums, target, begin, middle - 1);
            }
        }
    }

    // 找到的结果不一定是从左数起的第一个，所以要得到最终结果还要“Look around”
    public int[] lookAround(int[] nums, int index) {
        int left = index, right = index;
        for (int i = index; i >= 0; i--) {
            if (nums[i] == nums[index]) {
                left--;
            }
        }
        for (int i = index; i < nums.length; i++) {
            if (nums[i] == nums[index]) {
                right++;
            }
        }
        return new int[]{left + 1, right - 1};
    }
}

二分法思路很简单的，但是边界条件有点儿复杂，不过多尝试几次总会得到正确结果的。

五个月后。。。。

上面的二分查找和lookAround还是有些瑕疵，尤其是lookAround强行把时间拖到O（N），之前没注意这个问题，现在稍加改写。

二分查找2.0

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
40
41
42
43
44
45
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int index = binarySearch(nums, target, 0, nums.length - 1);
        if (index == -1) {
            return new int[]{-1, -1};
        }
        return lookAround(nums, index);
    }

    private int binarySearch(int[] nums, int target, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid = (start + end) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            return binarySearch(nums, target, mid + 1, end);
        } else {
            return binarySearch(nums, target, 0, mid - 1);
        }
    }

    private int[] lookAround(int[] nums, int index) {
        int left = index, right = index;
        for (int i = index; i >= 0; i--) {
            if (nums[i] == nums[index]) {
                left--;
            } else {
                break;
            }
        }
        for (int i = index; i < nums.length; i++) {
            if (nums[i] == nums[index]) {
                right++;
            } else {
                break;
            }
        }
        return new int[]{left + 1, right - 1};
    }
}

复杂度

一次遍历

  • 时间复杂度：O（N）
  • 空间复杂度：O（1）

二分查找

时间复杂度：O（log N）

空间复杂度：不考虑递归的话是O（1）