solution_python/031 Next Permutaion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 031 Next Permutaion\n",
    "- 学习时间：2020.7.15\n",
    "- 编程语言：python\n",
    "- 学习任务：leetcode题解\n",
    "- 题目地址：https://leetcode-cn.com/problems/next-permutation/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目:\n",
    "实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，\n",
    "则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 示例：\n",
    "- 示例 1:\n",
    "    ```\n",
    "    以下是一些例子，输入位于左侧列，其相应输出位于右侧列。\n",
    "    1,2,3 → 1,3,2\n",
    "    3,2,1 → 1,2,3\n",
    "    1,1,5 → 1,5,1\n",
    "    ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法一：**</font> [题解](https://leetcode-cn.com/problems/next-permutation/solution/ke-neng-shi-zui-jian-ji-de-pythonjie-da-by-luyao77/)  \n",
    "1. 从数组右侧向左开始遍历，找是否存在nums[i]>nums[i-1]的情况，\n",
    "2. 如果不存在这种nums[i]>nums[i-1]情况 ，for循环会遍历到i==0（也就是没有下一个排列），此时按题意排成有序Arrays.sort()\n",
    "3. 如果存在，则将从下标i到nums.length()的部分排序，然后在排过序的这部分中遍历找到第一个大于nums[i-1]的数，并与nums[i-1]交换位置\n",
    "```\n",
    "执行用时：44 ms, 在所有 Python3 提交中击败了53.35%的用户\n",
    "内存消耗：13.6 MB, 在所有 Python3 提交中击败了8.33%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： [1, 5, 1]\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums)-1, 0, -1):\n",
    "            if nums[i] > nums[i-1]:\n",
    "                nums[i:] = sorted(nums[i:])\n",
    "                for j in range(i, len(nums)):\n",
    "                    if nums[j] > nums[i-1]:\n",
    "                        nums[j], nums[i-1] = nums[i-1], nums[j]\n",
    "                        break\n",
    "                return\n",
    "        nums.sort()\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:  nums = [1,1,5]\n",
    "               output:  [1,5,1]\n",
    "\"\"\"\n",
    "nums = [1,1,5]\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.nextPermutation(nums)\n",
    "print('输出为：',nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法二：**</font> bisect模块，思路同方法一\n",
    " [题解](https://leetcode-cn.com/problems/next-permutation/solution/ke-neng-shi-zui-jian-ji-de-pythonjie-da-by-luyao77/)\n",
    "```\n",
    "执行用时：44 ms, 在所有 Python3 提交中击败了53.35%的用户\n",
    "内存消耗：13.7 MB, 在所有 Python3 提交中击败了8.33%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： [1, 5, 1]\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        index = len(nums) - 1\n",
    "        while index > 0:\n",
    "            if nums[index] > nums[index-1]:\n",
    "                break\n",
    "            index -= 1\n",
    "        \n",
    "        if index > 0:\n",
    "            nums[index:] = sorted(nums[index:])\n",
    "            swap_index = bisect.bisect(nums, nums[index-1], lo=index)\n",
    "            nums[swap_index], nums[index-1] = nums[index-1], nums[swap_index]\n",
    "        else:\n",
    "            nums.reverse()\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:  nums = [1,1,5]\n",
    "               output:  [1,5,1]\n",
    "\"\"\"\n",
    "nums = [1,1,5]\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.nextPermutation(nums)\n",
    "print('输出为：',nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "1. https://leetcode-cn.com/problems/next-permutation/solution/ke-neng-shi-zui-jian-ji-de-pythonjie-da-by-luyao77/"
   ]
  },
  {
   "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
}