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.
解题思路
- 先检查数组nums是否为null或者为空数组,若是则直接返回-1。
- 用二分法在数组中查找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; } }
good approach!