题目解析

两种方法的详细过程可参考文章:面试题

方法一:循环数组

  • 假设当前索引号为cur,则下一个挑礼物的小朋友索引号为new = cur + m - 1
  • 该小朋友不再回到圈内,从他下一个小朋友开始报数,因此他下一个小朋友的索引号为cur = new,即cur = cur + m - 1
  • 由于小朋友围成了圈,因此索引号还需对总人数取模,即cur = (cur + m - 1) % n
  • 每轮离开一个小朋友,直至只剩下一个小朋友。
  • 索引号记为当前剩余小朋友中的位置,编号则是小朋友原始的编号。题目要求输出剩下小朋友的编号,而计算过程是对岁引号进行操作,因此需要先存储每个编号对应的索引号。

代码实现

public int LastRemaining_Solution(int n, int m) {
        if(n == 0){
            return -1;
        }

        int cur = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0;i < n;i++){
            list.add(i);
        }
        while(n > 1){
            cur = (cur + m - 1) % n;
            list.remove(cur);
            n--;
        }
        return list.get(0);
    }
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

方法二:递推公式

反向递推。
定义F(n,m)表示最后剩下的小朋友的索引号,题目最终输出索引号对应的编号。推导F(n - 1,m):
以[0,1,2,3,4,5,6,7]为例,n = 8,m = 3,通过计算可知

F(8,3) = 6
F(7,3) = 3
F(6,3) = 0
F(5,3) = 3
F(4,3) = 0
F(3,3) = 1
F(2,3) = 1
F(1,3) = 0

通过反推可得(反推过程参考文章:面试题 ):
图片说明

public int LastRemaining_Solution(int n, int m) {
        if(n == 0){
            return -1;
        }

        int f = 0;
        for(int i = 2;i <= n;i++){
            f = (f + m) % i;
        }
        return f;
    }
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)