algorithms/031-next-permutation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "suited-envelope",
   "metadata": {},
   "source": [
    "实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。\n",
    "\n",
    "如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。\n",
    "\n",
    "必须 原地 修改，只允许使用额外常数空间。\n",
    "\n",
    "#### 示例 1：\n",
    "```\n",
    "输入：nums = [1,2,3]\n",
    "输出：[1,3,2]\n",
    "```\n",
    "#### 示例 2：\n",
    "```\n",
    "输入：nums = [3,2,1]\n",
    "输出：[1,2,3]\n",
    "```\n",
    "\n",
    "#### 示例 3：\n",
    "```\n",
    "输入：nums = [1,1,5]\n",
    "输出：[1,5,1]\n",
    "```\n",
    "\n",
    "#### 示例 4：\n",
    "```\n",
    "输入：nums = [1]\n",
    "输出：[1]\n",
    "```\n",
    "\n",
    "#### 提示：\n",
    "\n",
    "- `1 <= nums.length <= 100`\n",
    "- `0 <= nums[i] <= 100`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "id": "upper-macedonia",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "def solve2(nums: List[int]) -> None:\n",
    "    n = len(nums) - 1\n",
    "    i = n\n",
    "    while i > 0:\n",
    "        if nums[i] > nums[i - 1]:\n",
    "            break\n",
    "        i -= 1\n",
    "    \n",
    "    if i > 0:\n",
    "        j = n\n",
    "        while j >= 0:\n",
    "            if nums[j] > nums[i - 1]:\n",
    "                nums[i - 1], nums[j] = nums[j], nums[i - 1]\n",
    "                break\n",
    "            j -= 1\n",
    "\n",
    "    left, right = i, n\n",
    "    while left < right:\n",
    "        nums[left], nums[right] = nums[right], nums[left]\n",
    "        left += 1\n",
    "        right -= 1    \n",
    "    print(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "id": "communist-technique",
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(nums: List[int]) -> None:\n",
    "    n = len(nums) - 1\n",
    "    i = n\n",
    "    while i > 0 and nums[i] <= nums[i - 1]:\n",
    "        i -= 1\n",
    "    \n",
    "    if i > 0:\n",
    "        j = n\n",
    "        while j >= 0 and nums[j] <= nums[i - 1]:\n",
    "            j -= 1\n",
    "        nums[i - 1], nums[j] = nums[j], nums[i - 1]\n",
    "\n",
    "    left, right = i, n\n",
    "    while left < right:\n",
    "        nums[left], nums[right] = nums[right], nums[left]\n",
    "        left += 1\n",
    "        right -= 1    \n",
    "    print(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "id": "civilian-presentation",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 8, 5, 1, 3, 4, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "solve([1, 5, 8, 4, 7, 6, 5, 3, 1])     # [1, 5, 8, 5, 1, 3, 4, 6, 7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "id": "still-gasoline",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3, 2]\n"
     ]
    }
   ],
   "source": [
    "solve([1, 2, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "id": "crazy-iraqi",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "solve([3, 2, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "id": "material-overall",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 1]\n"
     ]
    }
   ],
   "source": [
    "solve([1, 1, 5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "id": "adverse-specification",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n"
     ]
    }
   ],
   "source": [
    "solve([1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "id": "critical-relationship",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 1, 3]\n"
     ]
    }
   ],
   "source": [
    "solve([1, 3, 2])   # [2, 1, 3]"
   ]
  }
 ],
 "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}