Leetcode(34) Find First and Last Position of Element in Sorted Array

发表于 | 分类于

Description

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

1
2
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

1
2
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

解法

看到O(logn)的时间复杂度，就要想到每次应该把处理的范围减半，这样一来，只有二分和树形结构能达到此目的，对于这个题目，当然是二分啦。可以先用二分查找查找到target，然后以target为中心向左右查找最早和最晚出现的节点。

具体代码如下：

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1, -1};
        if (nums.length == 0) {
            return res;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        int tmp = -1;
        while (start <= end) {
            mid = (start + end) / 2;
            if (nums[mid] == target) {
                tmp = mid;
                break;
            }
            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        if (tmp == -1) {
            return res;
        }
        int i = tmp;
        while (i >= 0) {
            if (nums[i] != target) {
                break;
            }
            res[0] = i;
            i--;
        }
        i = tmp;
        while (i < nums.length) {
            if (nums[i] != target) {
                break;
            }
            res[1] = i;
            i++;
        }
        return res;
    }
}

当然，严格而言，以上算法的时间复杂度的最坏情况O(n)，因为当所有元素均相同且为target需要遍历整个数组，这个时候为了达到严格的时间复杂度要求，可以以找到最小和找到最大的对应坐标为终止条件，更改终止条件代码，最小的index的特征有index = 0或nums[index-1]!=target，最大的条件同理。同时，若不满足该终止条件而又是target的话，若为寻找最小index，下一次搜索应该变化end，寻找最大index，下一次搜索应向右变化start，具体代码如下：

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
55
56
57
58
59
60
61
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1, -1};
        if (nums.length == 0) {
            return res;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        int tmp = -1;
        while (start <= end) {
            mid = (start + end) / 2;
            if (nums[mid] == target) {
                if (mid == 0) {
                    tmp = mid;
                    break;
                }
                if (mid - 1 >= 0) {
                    if (nums[mid - 1] != target) {
                        tmp = mid;
                        break;
                    }
                }
            }
            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        if (tmp == -1) {
            return res;
        }
        res[0] = tmp;
        start = 0;
        end = nums.length - 1;
        tmp = -1;
        while (start <= end) {
            mid = (start + end) / 2;
            if (nums[mid] == target) {
                if (mid == nums.length - 1) {
                    tmp = mid;
                    break;
                }
                if (mid + 1 <= nums.length - 1) {
                    if (nums[mid + 1] != target) {
                        tmp = mid;
                        break;
                    }
                }
            }
            if (nums[mid] <= target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        res[1] = tmp;
        return res;
    }
}