LeetCode34-在排序数组中查找元素的第一个和最后一个位置

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

中文链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

题目详述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

1
2
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

1
2
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

题目详解

  • ”数组 + 有序“可以联想到二分查找。
  • 找到数组中第一个大于或等于 target 的元素的下标，再找到数组中第一个大于 target 的元素的下标，就可以很容易得到目标值在数组中的开始位置和结束位置。
  • 在 C++ STL 中，找到数组中第一个大于或等于 target 的元素的下标可以用函数 lower_bound()，找到数组中第一个大于 target 的元素的下标可以用函数 upper_bound()。在 Java 中没有类似的 API，我们可以自己实现 lower_bound() 和 upper_bound()。
  • 实际上，LeetCode35-搜索插入位置 就是实现 lower_bound()，只不过 LeetCode35-搜索插入位置 假设数组中无重复元素，是 lower_bound() 的简化版。
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
public class LeetCode_00034 {

    public int[] searchRange(int[] nums, int target) {
        // 找到数组中第一个大于或等于 target 的元素的下标
        int left = lowerBound(nums, target);
        // 如果数组中存在等于 target 的元素，则寻找数组中第一个大于 target 的元素的下标
        if (left < nums.length && nums[left] == target) {
            int right = upperBound(nums, target);
            return new int[] { left, right - 1 };
        }
        // 数组中不存在目标值，返回 [-1, -1]
        return new int[] { -1, -1 };
    }

    /**
     * 返回数组中第一个大于或等于 target 的元素的下标。
     * 若数组中元素均小于 target，则返回数组最后一个元素的下一个位置的下标。
     * @param nums 已排序数组
     * @param target 目标值
     * @return 第一个大于或等于 target 的元素的下标
     */
    private int lowerBound(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    /**
     * 返回数组中第一个大于 target 的元素的下标。
     * 若数组中元素均小于或等于 target，则返回数组最后一个元素的下一个位置的下标。
     * @param nums 已排序数组
     * @param target 目标值
     * @return 第一个大于 target 的元素的下标
     */
    private int upperBound(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

我们也可以直接搜索目标值的开始位置和结束位置。

  • 假设目标值在闭区间 [l, r]中， 每次将区间长度缩小一半，当 l == r时，我们就找到了目标值。
  • 当我们将区间 [l, r] 划分成 [l, mid] 和 [mid + 1, r] 时，其更新操作是 r = mid 或者 l = mid + 1，计算 mid 时不需要加 1。first 不需要加 1。
  • 当我们将区间 [l, r] 划分成 [l, mid - 1] 和 [mid, r] 时，其更新操作是 r = mid - 1或者 l = mid，此时为了防止死循环，计算 mid 时需要加 1。last 不需要加 1。
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
public class LeetCode_00034 {

    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[] {-1, -1};
        }
        int left = first(nums, target);
        if (nums[left] != target) {
            return new int[] {-1, -1};
        }
        int right = last(nums, target);
        return new int[] {left, right};
    }

    private int first(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }

    private int last(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = (l + r + 1) >>> 1;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
}