LintCode 458. Last Position of Target 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/last-position-of-target/

Example

解题思路

1. 先检查数组nums是否为null或者为空数组，若是则直接返回-1。
2. 用二分法在数组中查找target值的位置。若查到了，不直接返回该target位置，而是继续以该位置开始向后面部分继续进行二分查找。以此来查找target在数组中出现的最后一个位置。

参考代码

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) { 
        // Write your code here 
        if (nums == null || nums.length == 0) { 
            return -1; 
        } 
         
        int start = 0; 
        int end = nums.length - 1; 
         
        while (start + 1 < end) { 
            int mid = start + (end - start) / 2; 
            if (nums[mid] == target) { 
                start = mid; 
            } else if (nums[mid] < target) { 
                start = mid; 
            } else { 
                end = mid; 
            }         
        } 
         
        if (nums[end] == target) { 
            return end;     
        } 
        if (nums[start] == target) { 
            return start; 
        } 
        return -1; 
    } 
}

相关题目

LintCode All in One 原创题目讲解汇总