大厂面试真题题解：目标最后位置

给一个升序数组，找到 target 最后一次出现的位置，如果没出现过返回 -1

在线评测地址：领扣题库官网

样例 1：
输入：nums = [1,2,2,4,5,5], target = 2
输出：2

样例 2：
输入：nums = [1,2,2,4,5,5], target = 6
输出：-1

算法：二分

算法思路

• 题目要求我们找到target最后一次出现的位置，由于数组是有序数组，我们可以考虑使用二分法来查找
  代码思路

1. 设置左边界等于0，右边界等于numsLen - 1
2. 对于mid所指向的数，当target < nums[mid]时，说明target在mid左侧，那么right = mid；否则说明target在mid右侧，或者如果target == nums[mid]的话说明mid还有可能存在target那么left = mid
3. 不断重复 2 直到 left + 1 == right 退出
4. 判断nums[right]是否等于target，若等于返回right，否则返回left，注意一定要先判nums[right]，因为nums[left]可能也等于target，但不是最后的位置

复杂度分析

NN表示nums数组长度

• 空间复杂度：O(1)
• 时间复杂度：O(logN)

public class Solution {

    /**
     * @param nums: An integer array sorted in ascending order
     * @param target: An integer
     * @return: An integer
     */

    public int lastPosition(int[] nums, int target) {
        if(nums == null || nums.length == 0)
            return -1;
        if(target < nums[0] || target > nums[nums.length-1])
            return -1;

        int left = 0, right = nums.length-1;

        while(left+1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > target)
                right = mid;
            else 
                left = mid;
        }

        if(nums[right] == target)
            return right;
        if(nums[left] == target)
            return left;
        return -1;
    }
}

更多题解参考：九章官网Solution