未分類

Next Permutation

Array, Go, LeetCode

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1
2
3
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
提示 解題應用
Array 規律觀查

Default:

1
2
3
func nextPermutation(nums []int)  {
}

解答思路:

一開始的想法是分成兩種情況來分別處理，一種可以透過位數互換找得到較大值，另一種則是結果本身就已經是最大值了，所以要將其做反轉，結果就是仍得不出其規律(較大值要離原值最近)，如果要找出一種方法來處理所有的情況，就處理極端的最大值來說一定需要反轉，那麼是不是其它情況在找較大值的時候，一邊確認後頭的位數是否已組成最大值，一邊找出最小能組出較大值的位數在哪一位(也就是當下一位數的值比現在位數的值小非為能組成的最大值)，找到該位數時後頭的位數確定已經是最大值，此時再將該位數的值與後頭最大值(個位數的值一定是最小)的每一位數做比較，從個位數開始找出比其大一點的值便與該位數交換位置，最後得到較大的該位數與後頭新組出的最大值，再將後頭的最大值反轉成為最小值，結果與原數相比就會是我們要的較大值。

程式碼解說:

因為是從個位數(陣列的最後頭)開始確認後頭是為為最大值，所以就從陣列的最後一個值與前一個值不斷做比較，直到index等於0為止，如果陣列前一個(下一位數字)比目前的值大，表示到下一位數為止是目前能組出的最大值，便將index減1往下一位檢查，而如果出現下一位數的值比現在位數的值小非為能組成的最大值，除了下一位數之外，到現在的位數都已經確定是最大值(個位數的值一定是最小)，再將該位數的值與確定最大值的每一位數做比較(從個位數開始)，如果發現較大的值便與該位數交換位置，接著跳開所有的迴圈，此時便得到較大的該位數與後頭新組出的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func nextPermutation(nums []int) {
	var tmp int
	index := len(nums) - 1
	for index > 0 {
		if nums[index] > nums[index-1] {
			for i := len(nums) - 1; i > index-1; i-- {
				if nums[i] > nums[index-1] {
					tmp = nums[i]
					nums[i] = nums[index-1]
					nums[index-1] = tmp
					break
				}
			}
			break
		}
		index--
	}
	...
}

最後則是將所有後頭組出的最大值做反轉成為最小值，只要從頭尾同時開始互換位置並逐漸向內移動，最後當頭的位置比尾的位置大時結束迴圈，便能得到後頭反轉後的最小值，整體的陣列結果就是我們要的較大值了

1
2
3
4
5
6
7
8
9
front := index
rear := len(nums) - 1
for front < rear {
	tmp = nums[front]
	nums[front] = nums[rear]
	nums[rear] = tmp
	front++
	rear--
}

完整程式碼:

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
func nextPermutation(nums []int) {
	var tmp int
	index := len(nums) - 1
	for index > 0 {
		if nums[index] > nums[index-1] {
			for i := len(nums) - 1; i > index-1; i-- {
				if nums[i] > nums[index-1] {
					tmp = nums[i]
					nums[i] = nums[index-1]
					nums[index-1] = tmp
					break
				}
			}
			break
		}
		index--
	}
	front := index
	rear := len(nums) - 1
	for front < rear {
		tmp = nums[front]
		nums[front] = nums[rear]
		nums[rear] = tmp
		front++
		rear--
	}
}

總結:

一陣列每個元素皆由0~9所組成，陣列上的位置分別表示一數字的每個位數，利用陣列上的元素組出只比原值稍大一點的結果，其做法是一邊確認後頭的位數是否已組成最大值，一邊找出最小能組出較大值的位數在哪一位(也就是當下一位數的值比現在位數的值小非為能組成的最大值)，找到該位數時後頭的位數確定已經是最大值，此時再將該位數的值與後頭最大值(個位數的值一定是最小)的每一位數做比較，從個位數開始找出比其大一點的值便與該位數交換位置，最後得到較大的該位數與後頭新組出的最大值，再將後頭的最大值反轉成為最小值，結果與原數相比就會是我們要的較大值。

分享到