31. 下一个排列

31. 下一个排列

代码

javascript

// 31. 下一个排列：https://leetcode.cn/problems/next-permutation/description/
// 输入：nums = [1,2,3]
// 输出：[1,3,2]

export function nextPermutation (nums) {
  let len = nums.length

  if (len <= 1) return

  let min = len - 2
  for (; min >= 0; min--) {
    if (nums[min] < nums[min + 1]) {
      break
    }
  }

  let max = len - 1
  for (; max > min && min >= 0; max--) {
    if (nums[max] > nums[min]) {
      break
    }
  }

  if (min >= 0) {
    [nums[min], nums[max]] = [nums[max], nums[min]]
  }

  for (let i = min + 1, j = len - 1; i < j; i++, j--) {
    [nums[i], nums[j]] = [nums[j], nums[i]]
  }
}

typescript

// 31. 下一个排列：https://leetcode.cn/problems/next-permutation/description/
// 输入：nums = [1,2,3]
// 输出：[1,3,2]

export function nextPermutation (nums: number[]): void {
  let len = nums.length

  if (len <= 1) return

  let min = len - 2
  for (; min >= 0; min--) {
    if (nums[min] < nums[min + 1]) {
      break
    }
  }

  let max = len - 1
  for (; max > min && min >= 0; max--) {
    if (nums[max] > nums[min]) {
      break
    }
  }

  if (min >= 0) {
    [nums[min], nums[max]] = [nums[max], nums[min]]
  }

  for (let i = min + 1, j = len - 1; i < j; i++, j--) {
    [nums[i], nums[j]] = [nums[j], nums[i]]
  }
}

测试代码

test

import { expect, test } from 'vitest'
import { nextPermutation } from './typescript.ts'
import { nextPermutation as nextPermutationJs } from './javascript.js'

test(`nextPermutation`, () => {
  const nums = [1,2,4,3]
  nextPermutation(nums)
  expect(nums).toEqual([1,3,2,4])
})

test(`nextPermutationJs`, () => {
  const nums = [1,2,4,3]
  nextPermutationJs(nums)
  expect(nums).toEqual([1,3,2,4])
})