力扣00031.下一个排列

发表于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 8 分钟
下一个排列、数组、双指针、中等

题目描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i == -1) {
            reverse(nums.begin(), nums.end());
            return;
        }
        int j = nums.size() - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        swap(nums[i], nums[j]);
        reverse(nums.begin() + i + 1, nums.end());
    }
};

结果

执行用时 : 0 ms, 击败 100.00% 使用 C++ 的用户

内存消耗 : 14.27 MB, 击败 5.56% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i == -1) {
            reverse(nums, 0, nums.length - 1);
            return;
        }
        int j = nums.length - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        swap(nums, i, j);
        reverse(nums, i + 1, nums.length - 1);
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 42.07 MB, 击败 22.67% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i == -1:
            nums.reverse()
            return
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = reversed(nums[i + 1:])

结果

执行用时 : 7 ms, 击败 99.57% 使用 Python 的用户

内存消耗 : 11.38 MB, 击败 96.34% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i == -1:
            nums.reverse()
            return
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = reversed(nums[i + 1:])

结果

执行用时 : 32 ms, 击败 96.03% 使用 Python3 的用户

内存消耗 : 16.47 MB, 击败 30.51% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void reverse(int* nums, int start, int end) {
    while (start < end) {
        swap(&nums[start], &nums[end]);
        start++;
        end--;
    }
}
void nextPermutation(int* nums, int numsSize) {
    int i = numsSize - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i == -1) {
        reverse(nums, 0, numsSize - 1);
        return;
    }
    int j = numsSize - 1;
    while (nums[j] <= nums[i]) {
        j--;
    }
    swap(&nums[i], &nums[j]);

    reverse(nums, i + 1, numsSize - 1);
}

结果

执行用时 : 3 ms, 击败 97.42% 使用 C 的用户

内存消耗 : 6.12 MB, 击败 92.04% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public void NextPermutation(int[] nums) {
        int i = nums.Length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i == -1) {
            Array.Reverse(nums);
            return;
        }
        int j = nums.Length - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        Swap(nums, i, j);
        Array.Reverse(nums, i + 1, nums.Length - i - 1);
    }
    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

结果

执行用时 : 100 ms, 击败 83.33% 使用 C# 的用户

内存消耗 : 46.14 MB, 击败 5.88% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i === -1) {
        nums.reverse();
        return;
    }
    let j = nums.length - 1;
    while (nums[j] <= nums[i]) {
        j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];
    reverse(nums, i + 1);
};
function reverse(nums, start) {
    let end = nums.length - 1;
    while (start < end) {
        [nums[start], nums[end]] = [nums[end], nums[start]];
        start++;
        end--;
    }
}

结果

执行用时 : 72 ms, 击败 42.58% 使用 JavaScript 的用户

内存消耗 : 51.04 MB, 击败 5.08% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 Do not return anything, modify nums in-place instead.
 */
function nextPermutation(nums: number[]): void {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i === -1) {
        nums.reverse();
        return;
    }
    let j = nums.length - 1;
    while (nums[j] <= nums[i]) {
        j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];
    reverse(nums, i + 1);
}
function reverse(nums: number[], start: number): void {
    let end = nums.length - 1;
    while (start < end) {
        [nums[start], nums[end]] = [nums[end], nums[start]];
        start++;
        end--;
    }
}

结果

执行用时 : 69 ms, 击败 62.28% 使用 TypeScript 的用户

内存消耗 : 52.34 MB, 击败 11.40% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function nextPermutation(&$nums) {
        $i = count($nums) - 2;
        while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) {
            $i--;
        }
        if ($i === -1) {
            $this->reverse($nums, 0);
            return;
        }
        $j = count($nums) - 1;
        while ($nums[$j] <= $nums[$i]) {
            $j--;
        }
        [$nums[$i], $nums[$j]] = [$nums[$j], $nums[$i]];
        $this->reverse($nums, $i + 1);
    }
    private function reverse(&$nums, $start) {
        $end = count($nums) - 1;
        while ($start < $end) {
            [$nums[$start], $nums[$end]] = [$nums[$end], $nums[$start]];
            $start++;
            $end--;
        }
    }
}

结果

执行用时 : 15 ms, 击败 30.77% 使用 PHP 的用户

内存消耗 : 20.43 MB, 击败 7.69% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    func nextPermutation(_ nums: inout [Int]) {
        var i = nums.count - 2
        while i >= 0 && nums[i] >= nums[i + 1] {
            i -= 1
        }
        if i == -1 {
            nums.reverse()
            return
        }
        var j = nums.count - 1
        while nums[j] <= nums[i] {
            j -= 1
        }
        nums.swapAt(i, j)
        var start = i + 1
        var end = nums.count - 1
        while start < end {
            nums.swapAt(start, end)
            start += 1
            end -= 1
        }
    }
}

结果

执行用时 : 12 ms, 击败 59.57% 使用 Swift 的用户

内存消耗 : 15.65 MB, 击败 6.38% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    fun nextPermutation(nums: IntArray): Unit {
        var i = nums.size - 2
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--
        }
        if (i == -1) {
            nums.reverse()
            return
        }
        var j = nums.size - 1
        while (nums[j] <= nums[i]) {
            j--
        }
        nums.swap(i, j)
        reverse(nums, i + 1)
    }
    private fun reverse(nums: IntArray, start: Int) {
        var end = nums.size - 1
        var s = start
        var e = end
        while (s < e) {
            nums[s] = nums[e].also { nums[e] = nums[s] }
            s++
            e--
        }
    }
    private fun IntArray.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
}

结果

执行用时 : 224 ms, 击败 21.74% 使用 Kotlin 的用户

内存消耗 : 38.23 MB, 击败 8.70% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  void nextPermutation(List<int> nums) {
    int i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      i--;
    }
    if (i >= 0) {
      int j = nums.length - 1;
      while (j >= 0 && nums[i] >= nums[j]) {
        j--;
      }
      _swap(nums, i, j);
    }
    _reverse(nums, i + 1, nums.length - 1);
  }
  void _swap(List<int> nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
  void _reverse(List<int> nums, int left, int right) {
    while (left < right) {
      int temp = nums[left];
      nums[left] = nums[right];
      nums[right] = temp;
      left++;
      right--;
    }
  }
}

结果

执行用时 : 318 ms, 击败 50.00% 使用 Dart 的用户

内存消耗 : 148.27 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func nextPermutation(nums []int) {
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }
    if i >= 0 {
        j := len(nums) - 1
        for j >= 0 && nums[i] >= nums[j] {
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    reverse(nums[i+1:])
}
func reverse(nums []int) {
    i, j := 0, len(nums)-1
    for i < j {
        nums[i], nums[j] = nums[j], nums[i]
        i++
        j--
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 2.27 MB, 击败 81.13% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# @param {Integer[]} nums
# @return {Void} Do not return anything, modify nums in-place instead.
def next_permutation(nums)
  i = nums.length - 2
  while i >= 0 && nums[i] >= nums[i + 1]
    i -= 1
  end
  if i >= 0
    j = nums.length - 1
    while j >= 0 && nums[i] >= nums[j]
      j -= 1
    end
    nums[i], nums[j] = nums[j], nums[i]
  end
  reverse(nums, i + 1)
end
def reverse(nums, start)
  i, j = start, nums.length - 1
  while i < j
    nums[i], nums[j] = nums[j], nums[i]
    i += 1
    j -= 1
  end
end

结果

执行用时 : 63 ms, 击败 -% 使用 Ruby 的用户

内存消耗 : 206.68 MB, 击败 100.00% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
object Solution {
  def nextPermutation(nums: Array[Int]): Unit = {
    var i = nums.length - 2
    while (i >= 0 && nums(i) >= nums(i + 1)) {
      i -= 1
    }
    if (i >= 0) {
      var j = nums.length - 1
      while (j >= 0 && nums(i) >= nums(j)) {
        j -= 1
      }
      swap(nums, i, j)
    }
    reverse(nums, i + 1, nums.length - 1)
  }
  private def swap(nums: Array[Int], i: Int, j: Int): Unit = {
    val temp = nums(i)
    nums(i) = nums(j)
    nums(j) = temp
  }
  private def reverse(nums: Array[Int], start: Int, end: Int): Unit = {
    var i = start
    var j = end
    while (i < j) {
      swap(nums, i, j)
      i += 1
      j -= 1
    }
  }
}

结果

执行用时 : 523 ms, 击败 33.33% 使用 Scala 的用户

内存消耗 : 55.04 MB, 击败 33.33% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
    pub fn next_permutation(nums: &mut Vec<i32>) {
        let mut i = nums.len() as i32 - 2;
        while i >= 0 && nums[i as usize] >= nums[(i + 1) as usize] {
            i -= 1;
        }
        if i >= 0 {
            let mut j = nums.len() as i32 - 1;
            while j >= 0 && nums[i as usize] >= nums[j as usize] {
                j -= 1;
            }
            nums.swap(i as usize, j as usize);
        }
        nums[(i + 1) as usize..].reverse();
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.09 MB, 击败 36.84% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户