LeetCode第31题：”下一个排列” C#篇

echo_sw

7个月前更新

理解题意：

这道题大概的意思是，将nums数组换一个排列方式，但要求比当前排列要大并且是当前数组大的排列中最小的一种排列

思路：

相信很多人看到这题第一个会想到的思路是，我只需要将这个数组所有比当前数组大的排列都整理出来，再选出最小的那一个排列，此题可解

很显然啊….这不是一个标准的答案，这个思路的时间复杂度是O(n!) 也就是n的阶乘,拿示例1举例n=3那么就是1*2*3=6,假设n=100或者1000或者更高所以….嗯….额你懂的对吧

我们应该可以把这个时间复杂度优化到O（N）,请各位观察下这两组数字

54321（排列前）

12345（排列后）

从上面数字中，我们看到单调递减的数字是无法得到这个解的，题目中的示例2也是如此，由此推测，正确答案是不是和单调递减有关系呢？

请再看下面这个示例

24534421（排列前）

24541234（排列后）

会发现我们从右往前数,我找到那位破坏单调递增的数字，再找到比这个数字大中最小的那个数字（注意是要靠后），交换位置，并将后面的数字升序排序即可

这里解释一下，为什么要从右往前数，因为调换越后面的数字，整个排列变化的值越小，这样是离正确答案最近的一条选项，请看下面例子

64564353（排列前）

64564533（排列后）

所以最后总结一下，我们仅需要五步，即可优化这个算法

1.先判断该数组是否可以排列，不能排列则直接返回，比如nums[]{1}

2.找到从右往左数破坏单调递增那个数字

3.如果nums是单调递减的，直接反转后返回，因为单调递减的nums无法得出解

4.找到比第二点这个数字大的最小的这个数字，并调换他们的位置

5.将调换位置后数字后面数字全部升序排序

代码：

 1  /// <summary>
 2  /// 下一个排列
 3  /// </summary>
 4  /// <param name="nums"></param>
 5  /// <returns></returns>
 6  public static int[] NextArrangement(int[] nums)
 7  {
 9      int len = nums.Length;
10      if (len==1)
11      {
12          return nums;
13      }
14      
15      int i = len - 2;
16      while (i >= 0 && nums[i] >= nums[i + 1])
17      {
18          i--;
19      }
20 
21      if (i<0) 
22      {
23          reverse(nums, 0, len - 1);
24          return nums;
25      }
26 
27      int lg = i + 1;
28 
29      while (lg < len && nums[lg]>nums[i])
30      {
31          lg++;
32      }
33      
34      swap(nums, i, lg - 1);
35      reverse(nums, i + 1, len - 1);
36      
37      return nums;
38  }
39 
40  /// <summary>
41  /// 交换数组中的两个元素
42  /// </summary>
43  /// <param name="nums"></param>
44  /// <param name="i">开始下标</param>
45  /// <param name="j">结束下标</param>
46  private static void swap(int[] nums, int i, int j)
47  {
48      int temp = nums[i];
49      nums[i] = nums[j];
50      nums[j] = temp;
51  }
52 
53  /// <summary>
54  /// 反转数组中的元素
55  /// </summary>
56  /// <param name="nums">数组</param>
57  /// <param name="start">开始下标</param>
58  /// <param name="end">结束下标</param>
59  public static void reverse(int[] nums, int start, int end)
60  {
61      while (start < end)
62      {
63          swap(nums, start++, end--);
64      }
65  }

使用：

 1 #region 下一个排序
 2 //int[] nums = new int[] { 2, 4, 5, 3, 4, 4, 2, 1 };
 3 int[] nums = new int[] { 6, 4, 5, 6, 4, 3, 5, 3 };
 4 for (int i = 0; i < nums.Length; i++)
 5 {
 6     Console.Write(nums[i]);
 7 }
 8 Console.WriteLine("");
 9 var result=Calculation.NextArrangement(nums);
10 for (int i = 0; i < result.Length; i++) 
11 {
12     Console.Write(result[i]);
13 }
14 Console.Read();
15 #endregion