[leetcode 390]Elimination Game原创解法

题目概述

leetcode现在支持Go了,这次用Go写一个算法题——消除游戏。

原题链接

You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:

Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
Keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Given the integer n, return the last number that remains in arr.

Example 1:

Input: n = 9

Output: 6

Explanation:

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]

arr = [2, 4, 6, 8]

arr = [2, 6]

arr = [6]

简单说就是从左至右消除,再从右到左消除,如果不唯一继续这个过程。对于这个例子,输入是9,那么开始就有1-9, 9个数。第一次,消除{1,3,5,7,9}, 第二次消除{8,4},第三次消除{2},最后留下数字6。

老办法,先用naive、暴力的方法求解,再优化。

暴力求解方法

基本思路就是

  1. 生成一个数组,含有1-n,n个整数。
  2. 从左到右消除,就是把偶数位置的数字依序移动到数组的左侧,并截取保留。例如从左至右消除数组[1,2,3,4,5,6,7,8,9], 移动偶数位置到左侧后,[2,4,6,8,5,6,7,8,9], 截取左侧后为[2,4,6,8]
  3. 从右至左消除,就是把奇数位置的数字依序移动到数组的右侧,并截取保留。例如从右至左消除数组[2,4,6,8],移动奇数 位置的数到右侧后,[2,4,2,6], 截取右侧后为[2,6]
  4. 如果不为1,继续步骤2

代码如下

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
34
//LastRemaining1 has time complexity O(n) and space complexity O(n)
func LastRemaining1(n int) int {
arr := gen(n)

leftToRight := true
for len(arr) > 1 {
if leftToRight {
for i := 1; i < len(arr); i += 2 {
arr[i/2] = arr[i]
}
length := len(arr) / 2
arr = arr[0:length]
} else {
count := 0
for i := 1; len(arr)-1-i >= 0; i += 2 {
arr[len(arr)-1-i/2] = arr[len(arr)-1-i]
count += 1
}
arr = arr[len(arr)-count:]
}

leftToRight = !leftToRight
}

return arr[0]
}

func gen(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i + 1
}
return arr
}

这个时间和空间复杂度都是 O(n)\mathcal{O}(n) ,空间复杂度是 O(n)\mathcal{O}(n) 好理解。那么时间复杂度是怎么计算的呢? 对于输入n,第一次消除遍历 n2\dfrac{n}{2} ,第二次消除遍历 n22\dfrac{n}{2^2} , 第三次消除遍历n23\dfrac{n}{2^3} …因此总时间就是

n2+n22+n23+n\dfrac{n}{2} + \dfrac{n}{2^2} + \dfrac{n}{2^3} + \ldots \approx n

分析和优化后的算法

暴力解法直观,但是空间占用太多了,当n很大的时候,直接栈溢出了。那么该怎么优化呢。只能是找规律,通过发现递推关系来求解。

也就是说,假如我们要求解的函数为y=f(n)y=\mathcal{f}(n),其中n就是输入的自然数。y为剩余的最后的数字。 根据以往的经验我们考虑分治法,找到递推关系 f(n+1)=anf(n)+an1f(n1)+\mathcal{f}(n+1) = a_n\mathcal{f}(n) + a_{n-1}\mathcal{f}(n-1) + \ldots

很显然,我们知道 f(1)=1\mathcal{f}(1) = 1 , f(2)=2\mathcal{f}(2) = 2 , f(3)=2\mathcal{f}(3) = 2

通过观察,我们可以发现这样一个递归过程,经过一轮从左至右和从右至左的消除后,余下一个长度为n4\dfrac{n}{4} 的新的数列。 如果长度n43\dfrac{n}{4} \leq 3 ,那么可以直接知道f(n4)\mathcal{f}(\dfrac{n}{4}) 的值,该值就是新数列的编号。 取出新数列的该编号的值并返回。 如果数列的长度大于3,那么返回新数列中编号为 f(n4)\mathcal{f}(\dfrac{n}{4}) 的数字。

也就是说我们发现了递推关系 f(n)=operatorf(n4)\mathcal{f}(n) = operator*\mathcal{f}(\dfrac{n}{4})

举例说明我们的递归过程,当n=9时,经过一轮从左至右和从右至左的消除后,余下一个长度为2的数列[2,6], 因为f(2)=2\mathcal{f}(2) = 2 , 所以返回数列[2,6]编号为2的数,也就是数字6。

代码实现如下

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
//LastRemaining2 has time complexity O(log(n)) and space complexity O(log(n))
//Runtime: 3 ms, faster than 85.71% of Go online submissions for Elimination Game.
//Memory Usage: 2.6 MB, less than 97.62% of Go online submissions for Elimination Game.
func LastRemaining2(n int) int {
return f(n)
}

func f(n int) int {
if n == 1 {
return 1
}
if n == 2 || n == 3 {
return 2
}

//经过一轮从左至右和从右至左消除后
last := last(n) //数列的最后一个数字
length := length(n) //数列的长度
return last - 4*(length-f(length)) //返回数列中,编号为f(length)的数字
}

func last(n int) int {
return n - (n % 2) - 2
}

func length(n int) int {
n /= 2
n /= 2
return n
}

时间复杂度和空间复杂度都是 O(logn)\mathcal{O}(\log{}n) ,因为递归调用的次数为 log4n=logn2\log_{4}n = \dfrac{\log{}n}{2}