圆圈中最后剩下的数字

题目描述

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

思路

1.模拟游戏过程，需要设置一个删除索引delIndex，初始值为0，每次与m相加，然后结果-1；即delIndex = delIndex+ m -1。
2.当delIndex超过数组长度时，说明要回到头部，我们直接取余即可。
3.当数组只剩下一个元素时，就是我们需要的答案。

Java代码实现

class Solution {
    public int lastRemaining(int n, int m) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int delIndex = 0;
        while(list.size()>1){
            delIndex = delIndex + m - 1;
            
            if(delIndex >= list.size()){
                delIndex = delIndex % list.size();
            }
            
            list.remove(delIndex);
        }
        
        return list.get(0);
    }
}

Golang代码实现

func lastRemaining(n int, m int) int {
    delIndex := 0

    numSlice := make([]int,n)

    for i:=0; i<n; i++ {
        numSlice[i] = i
    }
    for len(numSlice) > 1 {
        delIndex = delIndex + m - 1
        if delIndex >= len(numSlice) {
            delIndex = delIndex % len(numSlice)
        }
        numSlice = append(numSlice[0:delIndex],numSlice[delIndex+1:]...)
    }

    return numSlice[0]
}