LeetCode.下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解法：

object NextPermutation {

     def main(args: Array[String]): Unit = {
          val nums0 = Array(3, 4, 1, 4, 3, 3)
          solution(nums0)
          println(java.util.Arrays.toString(nums0))

          val nums = Array(2, 3, 1, 3, 3)
          solution(nums)
          println(java.util.Arrays.toString(nums))

          val nums2 = Array(1, 6, 2, 5, 3, 7, 4)
          solution(nums2)
          println(java.util.Arrays.toString(nums2))

          val nums3 = Array(2, 2, 7, 5, 4, 3, 2, 2, 1)
          solution(nums3)
          println(java.util.Arrays.toString(nums3))
     }

     def solution(nums: Array[Int]): Unit = {
          if (nums.length == 1) return
          val size = nums.length
          if (nums(size - 1) > nums(size - 2)) {
               swap(nums, size - 1, size - 2)
               return
          }

          //找到从后向前第一个减小的数x
          var index = -1
          var i = size - 1
          while (i > 0 && index < 0) {
               if (nums(i - 1) < nums(i)) {
                    index = i - 1
               }
               i -= 1
          }

          //没找到，说明是降序，直接反转返回
          if (index == -1) {
               for (i <- 0 until size / 2) {
                    swap(nums, i, size - 1 - i)
               }
               return
          }

          //找到x之后找到y，是的y = Min({? > x})
          var min = index + 1
          for (i <- index + 1 until size) {
               if (nums(i) > nums(index) && nums(min) > nums(i)) {
                    min = i
               }
          }
          swap(nums, index, min)

          //把x之后的数据按升序排序
          for (i <- index + 1 until size - 1) {
               for (j <- i + 1 until size) {
                    if (nums(j) < nums(i)) {
                         swap(nums, i, j)
                    }
               }
          }
     }

     def swap(nums: Array[Int], i: Int, j: Int): Unit = {
          val tmp = nums(i)
          nums(i) = nums(j)
          nums(j) = tmp
     }
}