大廠面試真題題解：目标最後位置

給一個升序數組，找到 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