刷题日记 24.5.3

lc34. 在排序数组中查找元素的第一个和最后一个位置（MD）

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

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

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 是一个非递减数组
• -10^9 <= target <= 10^9

---

其实就是对查找元素的左右边界做二分查找

实际上，可以把查找左右边界拆成两个函数，但是我没整出来；力扣的官方题解是写成一个函数，但我觉得这么写容易混淆，不易于理解

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = getLeftBound(nums, target), r = getRightBound(nums, target);
        if (l == -2 || r == -2) {
            return {-1, -1};
        } else if (r - l > 1) {
            return {l + 1, r - 1};
        } else {
            return {-1, -1};
        }
    }
private:
    int getLeftBound(const vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        int res = -2;
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
                r = mid - 1;
                res = r;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }

    int getRightBound(const vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        int res = -2;
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] <= target) {
                l = mid + 1;
                res = l;
            } else {
                r = mid - 1;
            }
        }
        return res;
    }
};

---

lc153. 寻找旋转排序数组中的最小值（MD）

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数 互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

---

必须设计一个时间复杂度为 O(log n) 的算法，那么明显就是要求用二分了

如果不用二分的话，一次遍历也能找出来，时间复杂度就是 o(n) ，但是不符合这道题的要求

class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] < nums[r]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
}

就是常规的二分法

---

lc215. 数组中的第k个最大元素（MD）

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

---

这道题偷个懒，直接用java自带的优先队列做这道题

（实际上，面试中是不允许候选人直接使用现成的优先队列的，这时候只能考虑使用类似于快排的方法或者手写一个优先队列）

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        for (int i = 0; i < n; i++) {
            heap.offer(nums[i]);
        }

        for (int i = 1; i < k; i++) {
            heap.poll();
        }
        return heap.peek();
    }
}