关于express:2023大厂算法面试真题手刷笔记含社区7大语言最佳答案No34在排序数组中查找元素的第一个和最后一个位置

42次阅读

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

题目详情

给你一个依照非递加顺序排列的整数数组 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 <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递加数组
  • -109 <= target <= 109

解题思路

办法 1 线性查找

首先，咱们从右边对 nums 进行线性扫描，当咱们找到一个指标实例时就会中断。如果咱们从不中断，那么指标就不存在，所以咱们能够提前返回“-1，-1”的“错误代码”。思考到咱们的确找到了一个无效的左索引，咱们能够进行第二次线性扫描，但这次从右开始。在这种状况下，遇到的指标的第一个实例将是最左边的实例（并且因为存在最右边的实例，因而也保障存在最左边的实例）。而后咱们简略地返回一个蕴含两个定位索引的列表。

class Solution {public int[] searchRange(int[] nums, int target) {int[] targetRange = {-1, -1};

        // find the index of the leftmost appearance of `target`.
        for (int i = 0; i < nums.length; i++) {if (nums[i] == target) {targetRange[0] = i;
                break;
            }
        }

        // if the last loop did not find any index, then there is no valid range
        // and we return [-1, -1].
        if (targetRange[0] == -1) {return targetRange;}

        // find the index of the rightmost appearance of `target` (by reverse
        // iteration). it is guaranteed to appear.
        for (int j = nums.length-1; j >= 0; j--) {if (nums[j] == target) {targetRange[1] = j;
                break;
            }
        }

        return targetRange;
    }
}

办法二 二分查找

除了用于查找左右索引自身的子例程之外，整体算法与线性扫描办法的工作形式十分类似。, 在这里，咱们应用批改后的二分查找来搜寻已排序的数组，并进行一些小的调整。, 首先，因为咱们正在定位蕴含指标的最右边（或最左边）索引（而不是在咱们找到指标时返回 true），所以算法一找到匹配就不会终止。, 相同，咱们持续搜寻直到 lo == hi 并且它们蕴含能够找到指标的索引。

, 另一个变动是引入了左参数，这是一个布尔值，示意在 target == nums [mid] 的事件中要做什么;, 如果右边是真的，那么咱们在关系上的左子数组上“递归”, 否则，咱们在右子数组上递归。要理解为什么这是正确的，请思考咱们在索引 i 处找到指标的状况。, 最右边的指标不能呈现在大于 i 的任何索引处，因而咱们永远不须要思考正确的子阵列。, 雷同的参数实用于最左边的索引。

class Solution {// returns leftmost (or rightmost) index at which `target` should be
    // inserted in sorted array `nums` via binary search.
    private int extremeInsertionIndex(int[] nums, int target, boolean left) {
        int lo = 0;
        int hi = nums.length;

        while (lo < hi) {int mid = (lo + hi) / 2;
            if (nums[mid] > target || (left && target == nums[mid])) {hi = mid;}
            else {lo = mid+1;}
        }

        return lo;
    }

    public int[] searchRange(int[] nums, int target) {int[] targetRange = {-1, -1};

        int leftIdx = extremeInsertionIndex(nums, target, true);

        // assert that `leftIdx` is within the array bounds and that `target`
        // is actually in `nums`.
        if (leftIdx == nums.length || nums[leftIdx] != target) {return targetRange;}

        targetRange[0] = leftIdx;
        targetRange[1] = extremeInsertionIndex(nums, target, false)-1;

        return targetRange;
    }
}

社区最佳答案

编程语言：java
运行工夫：4ms
战败比例：beat 100%

class Solution {public int[] searchRange(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        int[] res = new int[2];
        Arrays.fill(res, -1);
        while (start <= end) {int mid = start + (end - start) / 2;
            if (nums[mid] < target) {start = mid + 1;} else if (nums[mid] > target) {end = mid - 1;}
//            if (nums[start] == target && res[0] == -1) {//                res[0] = start;
//                while (mid <= end) {
//
//                }
//            }
            if (nums[mid] == target) {res[0] = findFirst(nums, start, mid, target);
                res[1] = findEnd(nums, mid, end, target);
                return res;
//                int temp = mid;
//                while (start <= mid) {//                    temp = start + (temp - start) / 2;
//                    if (nums[temp] < target) {
//                        start = temp + 1;
//                    }
//
//                    if (start == mid
//                            || (nums[start] == target && (start - 1 < 0 || nums[start - 1] < target))) {//                        res[0] = start;
//                        break;
//                    } else if (start == temp) {
//                        start++;
//                    }
//                }
//
//                temp = mid;
//                while (mid <= end) {//                    temp = temp + (end - temp) / 2;
//                    if (nums[temp] > target) {
//                        end = temp - 1;
//                    }
//
//                    if (temp == mid
//                            || nums[temp] == target && (temp + 1 >= nums.length || nums[temp + 1] > target)) {//                        res[1] = temp;
//                        break;
//                    } else if (temp == end) {
//                        end--;
//                    }
//                }
//
//                return res;
            }
        }
        return res;
    }

    private int findFirst(int[] nums, int start, int end, int target) {while (start < end) {int temp = start + (end - start) / 2;
            if (nums[temp] < target) {start = temp + 1;} else if (nums[temp] == target) {end = temp;}
        }

        return start;
    }

    private int findEnd(int[] nums, int start, int end, int target) {while (start < end) {int temp = start + (end - start + 1) / 2;
            if (nums[temp] > target) {end = temp - 1;} else if (nums[temp] == target) {start = temp;}
        }

        return start;
    }
}

编程语言：javascript
运行工夫：52ms
战败比例：beat 100%

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
let searchRange = function(nums, target) {
    let sl = 0;
    let sm = 0;
    let sr = nums.length - 1;
    let el = 0;
    let em = 0;
    let er = nums.length - 1;
    while (sl < sr || el < er) {if (sl < sr) {sm = Math.floor((sl + sr) / 2);
            if (nums[sm] < target) {sl = sm + 1;} else {sr = sm;}
        }
        
        if (el < er) {em = Math.ceil((el + er) / 2);
            if (nums[em] > target) {er = em - 1;} else {el = em;}
        }
    }
    return nums[sl] === target ? [sl, er] : [-1, -1];
};

编程语言：python
运行工夫：24ms
战败比例：beat 100%

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return [-1, -1]
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) / 2
            if nums[mid] == target:
                left = mid
                right = mid
                while left >= 0 and nums[left] == target:
                    left -= 1
                while right <= len(nums) - 1 and nums[right] == target:
                    right += 1
                return [left + 1, right - 1]
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        return [-1,-1]

编程语言：python3
运行工夫：40ms
战败比例：beat 100%

class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        def binary_find(nums,left,right,k):
            res = [-1,-1]
            if not nums:return res
            while left<right and nums[left]!=nums[right]:
                mid = (left+right)//2
                if nums[mid]==k:
                    if nums[left]<k:
                        left += 1
                    if nums[right]>k:
                        right -=1
                elif nums[mid]<k:
                    left = mid+1
                else: right = mid-1
            if nums[left]==k and nums[right]==k:
                return [left,right]
            else:return [-1,-1]
        return binary_find(nums,0,len(nums)-1,target)

编程语言：cpp
运行工夫：4ms
战败比例：beat 100%

static const auto _____ = []() {ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {vector<int> resultVec(2, -1);
        int indexPre;
        if ((resultVec[0] = Findpre(nums, target)) != -1) {resultVec[1] = FindLast(nums, target);
        }
        return resultVec;
    }
    int Findpre(vector<int>&nums, int target) {
        int low = 0;
        int high = nums.size() - 1;
        while (low <= high) {int middle = (low + high) / 2;
            if (nums[middle]<target)
                low = middle + 1;
            if (nums[middle]>target)
                high = middle - 1;
            if (nums[middle] == target) {if (middle - 1 == -1 || nums[middle - 1]<target)
                    return middle;
                else {high = middle - 1;}
            }
        }
        return -1;
    }
    int FindLast(vector<int>&nums, int target) {
        int low = 0;
        int high = nums.size() - 1;
        while (low <= high) {int middle = (low + high) / 2;
            if (nums[middle]<target)
                low = middle + 1;
            if (nums[middle]>target)
                high = middle - 1;
            if (nums[middle] == target) {if (middle + 1 == nums.size() || nums[middle + 1]>target)
                    return middle;
                else {low = middle + 1;}
            }
        }
        return -1;
    }
};

编程语言：c
运行工夫：4ms
战败比例：beat 100%

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    int *res;
    *returnSize = 2;
    res = (int*)malloc(sizeof(int) * 2);
    res[0] = -1;
    res[1] = -1;
    int i;
    int flag = 0; // 开始标记
    for (i = 0; i < numsSize; i++) {if (nums[i] == target  && !flag) {res[0] = i;
            flag = 1;
        }
        if (nums[i] == target && flag &&(i==numsSize-1 || i<numsSize-1 && nums[i+1]>target)) {*(res + 1) = i;
            break;
        }
    }
    return res;
}

编程语言：swift
运行工夫：16ms
战败比例：beat 100%

class Solution {func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        var left = 0
    var right = nums.count - 1
    var mid = 0
    var first = -1
    
    // 寻找第一个呈现 target 的地位
    while left <= right {mid = left + (right - left)/2
        if nums[mid] >= target {right = mid - 1} else {left = mid + 1}
        if nums[mid] == target {first = mid}
    }
    
    // 如果找不到第一个间接返回
    if first == -1 {return [first ,first]
    }
    
    // 寻找最初一个呈现 target 的地位
    var last = -1
    left = first
    right = nums.count - 1
    while left <= right {mid = left + (right - left)/2
        if nums[mid] > target {right = mid - 1} else {left = mid + 1}
        if nums[mid] == target {last = mid}
    }
    return [first,last]
    }
}

参考资料

文内各种编程语言的最佳答案参考自“算法面试宝典”小程序，小程序内每个题目都有具体的解题报告，还有大厂面试真题，值得一用。wx 扫码可关上。

正文完
express
发表至： express
2023-05-18
 0
关于express:CompletableFuture实现异步编排
关于express:大屏开发你需要知道哪些
关于express:任务编排CompletableFuture从入门到精通
关于express:面试官什么是双亲委派模型