solution_python/034  Find First and Last Position of Element in Sorted Array.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 034  Find First and Last Position of Element in Sorted Array\n",
    "- 学习时间：2020.7.20\n",
    "- 编程语言：python\n",
    "- 学习任务：leetcode题解\n",
    "- 题目地址：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目:\n",
    "给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。  \n",
    "你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 示例：\n",
    "- 示例 1:\n",
    "    ```\n",
    "    输入: nums = [5,7,7,8,8,10], target = 8\n",
    "    输出: [3,4]\n",
    "    ```\n",
    "- 示例 2:\n",
    "    ```\n",
    "    输入: nums = [5,7,7,8,8,10], target = 6\n",
    "    输出: [-1,-1]\n",
    "    ```   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法一：**</font> 线性扫描 [题解](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-yi-/)  \n",
    "```\n",
    "执行用时：32 ms, 在所有 Python3 提交中击败了97.66%的用户\n",
    "内存消耗：14.7 MB, 在所有 Python3 提交中击败了7.69%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： [3, 4]\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        # find the index of the leftmost appearance of `target`. if it does not\n",
    "        # appear, return [-1, -1] early.\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == target:\n",
    "                left_idx = i\n",
    "                break\n",
    "        else:\n",
    "            return [-1, -1]\n",
    "\n",
    "        # find the index of the rightmost appearance of `target` (by reverse\n",
    "        # iteration). it is guaranteed to appear.\n",
    "        for j in range(len(nums)-1, -1, -1):\n",
    "            if nums[j] == target:\n",
    "                right_idx = j\n",
    "                break\n",
    "\n",
    "        return [left_idx, right_idx]\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:  nums = [5,7,7,8,8,10], target = 8\n",
    "               output:  [3,4]\n",
    "\"\"\"\n",
    "nums = [5,7,7,8,8,10]\n",
    "target = 8\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.searchRange(nums, target)\n",
    "print('输出为：', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法二：**</font> 二分查找 [题解](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-yi-/)  \n",
    "```\n",
    "执行用时：52 ms, 在所有 Python3 提交中击败了16.85%的用户\n",
    "内存消耗：14.5 MB, 在所有 Python3 提交中击败了7.69%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： [3, 4]\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    # returns leftmost (or rightmost) index at which `target` should be inserted in sorted\n",
    "    # array `nums` via binary search.\n",
    "    def extreme_insertion_index(self, nums, target, left):\n",
    "        lo = 0\n",
    "        hi = len(nums)\n",
    "\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if nums[mid] > target or (left and target == nums[mid]):\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid+1\n",
    "\n",
    "        return lo\n",
    "\n",
    "\n",
    "    def searchRange(self, nums: List[int], target: int) -> List[int]:\n",
    "        left_idx = self.extreme_insertion_index(nums, target, True)\n",
    "\n",
    "        # assert that `left_idx` is within the array bounds and that `target`\n",
    "        # is actually in `nums`.\n",
    "        if left_idx == len(nums) or nums[left_idx] != target:\n",
    "            return [-1, -1]\n",
    "\n",
    "        return [left_idx, self.extreme_insertion_index(nums, target, False)-1]\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:  nums = [5,7,7,8,8,10], target = 8\n",
    "               output:  [3,4]\n",
    "\"\"\"\n",
    "nums = [5,7,7,8,8,10]\n",
    "target = 8\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.searchRange(nums, target)\n",
    "print('输出为：', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "1. https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 如果你觉得有用的话：\n",
    "- 请点点 **star** 呦\n",
    "- 关注我的 [CSDN博客](https://mp.csdn.net/console/article)\n",
    "- 关注我的 [哔哩哔哩](https://space.bilibili.com/424394389/channel/detail?cid=132513)\n",
    "- 关注公众号：CV伴读社\n",
    "<img src='./images/qrcode.jpg' style='zoom:100%'>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}