圆圈中最后剩下的数

1. 题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

2. 思路

• 模拟法
• 递归法
• 迭代法

3. 实现

3.1. 模拟法

//空间：O(N)
//时间：O(N²)
func LastRemaining_Solution(n int, m int) int {
	if n <= 0 || m <= 0 {
		return -1
	}
	queue := make([]int, 0)
	for i := 0; i < n; i++ {
		queue = append(queue, i)
	}

	index := 0
	for len(queue) != 1 {
	    //这段类似于循环队列的下标操作
		index = (index + m - 1) % len(queue)
		queue = remove(queue, index)
	}
	return queue[0]
}

func remove(a []int, i int) []int {
	newData := make([]int, 0)
	newData = append(newData, a[:i]...)
	newData = append(newData, a[i+1:]...)

	return newData
}

3.2. 递归法

//空间：O(N)
//时间：O(N)
func LastRemaining_Solution2(n int, m int) int {
	if n <= 0 || m <= 0 {
		return -1
	}

	return f(n, m)
}

func f(n int, m int) int {
	if n == 1 {
		return 0
	}
	x := f(n-1, m)
	return (x + m) % n
}

3.3. 迭代法

//时间复杂度：O(N)
//空间复杂度: O(1)
func LastRemaining_Solution3(n int, m int) int {
	if n <= 0 || m <= 0 {
		return -1
	}

	index := 0
	for i := 2; i <= n; i++ {
		index = (index + m) % i
	}
	return index
}

4. 参考

• 孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网