[leetcode/lintcode 题解] 目标最后位置

zzzrf:给一个升序数组,找到 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;
    }
}

[leetcode/lintcode 题解] 算法模板:二分查找

zzzrf:给定一个排序的整数数组(升序)和一个要查找的整数 target,用 O(logn)的时间查找到 target 第一次出现的下标(从 0 开始),如果 target 不存在于数组中,返回-1 。 在线做题地址 样例 1: 输入:[1,4,4,5,7,7,8,9,9,10],1 输出: 0 样例解释: 第一次出现在第 0 个位置。 样例 2: 输入:…

刷 LeetCode/LintCode 的一些心得

zzzrf:我之前就是完全 0 基础、大龄转码,刷题上千然后进谷歌的…… 这里 0 基础指的是没学过编程语言,没学过数据结构和算法,一上来就直接做题那种。 第一道题 two sum,我显然不会做。**我的笨方法就是看答案,背答案,然后默出来,就这样还是错了很多次。 然而就是这样低的起点,我把 LC 前 300 道题刷了至少 3 遍,累计刷题数超过 1000 …

LeetCode题解计算机为什么是基于二进制的?

可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制

LeetCode题解统计城市的所有灯泡

这个是我刚毕业的时候,一个真实的面试题,这是一个开放题。题目描述:想办法,将一个城市的所有灯泡数量统计出来。题解:费米估算法1、如果某个城市常驻人口有1000万2、假设每5人居住在一套房里,每套房有灯泡5只,那么住宅灯泡共有1000万只3、假设公众场所每10人共享一只灯泡,那么共有100万只4、主要的这两者相加就得出了1100万只当然实际上这是估算的,具体应…

LeetCode题解黑白圆盘

一个圆盘被涂上了黑白二色,两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解:可以用一个相机即可