关于java:LeetCode034在排序数组中查找元素的第一个和最后一个位置

3次阅读

共计 1429 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：给定一个依照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始地位和完结地位。

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

进阶：

你能够设计并实现工夫复杂度为 O(log n) 的算法解决此问题吗？

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：二分查找、递归

用 left 和 right 记录开始地位和完结地位，用二分查找法查找 target 在 nums 中的地位，从 0 到 nums.length- 1 别离记为 low 和 high，mid 示意两头值，具体过程如下：

计算 mid 为 low 和 high 的两头值；

如果 mid 的值和 target 相等，则判断 mid 右边的元素是否跟 target 相等，如果相等，则递归查找开始地位，从 low 到 mid- 1 查找，如果不相等，则 left 为 mid；判断 mid 左边的元素是否跟 target 相等，如果相等，则递归查找完结地位，从 mid+ 1 到 high 查找，如果不相等，则 right 为 mid；

如果 mid 的值大于 target，则 high 更新为 mid-1；

如果 mid 的值小于 target，则 low 更新为 mid+1。

查找实现后返回 left 和 right 即为最终后果。

import javafx.util.Pair;

public class LeetCode_034 {public static int[] searchRange(int[] nums, int target) {Pair<Integer, Integer> result = find(nums, 0, nums.length - 1, target);
        return new int[]{result.getKey(), result.getValue()};
    }

    public static Pair<Integer, Integer> find(int[] nums, int low, int high, int target) {
        int mid, left = -1, right = -1;
        while (low <= high) {mid = (low + high) / 2;
            if (nums[mid] == target) {if (mid + 1 <= high && nums[mid + 1] == nums[mid]) {right = find(nums, mid + 1, high, target).getValue();} else {right = mid;}
                if (mid - 1 >= low && nums[mid - 1] == nums[mid]) {left = find(nums, low, mid - 1, target).getKey();} else {left = mid;}
                break;
            } else if (nums[mid] > target) {high = mid - 1;} else {low = mid + 1;}
        }
        return new Pair<>(left, right);
    }

    public static void main(String[] args) {int[] nums = new int[]{5, 7, 7, 8, 8, 10};
        int[] ints = searchRange(nums, 8);
        System.out.println("[" + ints[0] + "," + ints[1] + "]");
    }
}