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

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

问题描述

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

Find the last position of a target number in a sorted array. Return -1 if target does not exist.

Example

Given [1, 2, 2, 4, 5, 5].

For target = 2, return 2.

For target = 5, return 5.

For target = 6, return -1.

解题思路

  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 原创题目讲解汇总

One Thought to “LintCode 458. Last Position of Target 原创Java参考解答”

发表评论

您的电子邮箱地址不会被公开。