约瑟夫环问题

在刷leetCode 的时候碰到了以下问题:
给定一个从1 到 n 排序的整数列表。
首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。
第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。
我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
返回长度为 n 的列表中，最后剩下的数字。

示例：

输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

输出:
6

学过数据结构的同学肯定知道这个就是大名鼎鼎的约瑟夫环问题。
我们先按照自己的想法处理这个约瑟夫环问题:
这种问题一般是有规律的,但是我们先不考虑此问题的规律性,先按照一般逻辑处理这个算法问题:
简单的逻辑:模拟计算,我需要的正序取一遍,倒序再取,直到整个数组只有一个数字为止,输出这个数字.
1 2 3 4 5 6 7 8 9 ···· 正序取出的是 %2 = 1 的数
＞
2 4 6 8 ···· 倒序后取出的 %2 = 1 的数
＜
2 6 ···· 正序后取出的 %2 = 1 的数
＞
6

这个问题就简单了,每次将数组的顺序倒过来之后再取位置 %2 = 1 的数字即可:
为了简便我们先使用JS来书写代码:

var lastRemaining = function(n) {
    let a = [];

    for (var i = 1; i <= n; i ++) {
        a.push(i);
    }
    var h = dealWithArr(a, 1);
    return h;
};

// 通过迭代完成取值
var dealWithArr = function (list,isPostiveSeq){
    if (list.length == 1) {
        var a = list[0];
        return  a;
    }
    var newList = [];
    var j = 0;
   // 正序和反序时取值
    for(var i = isPostiveSeq?0:list.length -1; (isPostiveSeq? i < list.length : i >= 0);isPostiveSeq? i++ : i-- ) {
        if (j %2 == 1) {
            newList.push(list[i]);
        }
        j ++;
    }
    return dealWithArr(newList, 0);
}

image.png

在值比较小的时候,执行程序没有什么问题,但是当值过大的时候就会发现出现内存溢出

image.png

不过,动动脑子也能想到,如果能不动脑解决算法问题,还要做算法分析干什么,还是老老实实来分析

我们分奇偶两种情况来考虑。先考虑整个N是偶数的情况:
1 2 3 4 5 6 …… 2k-3 2k-2 2k-1 2k
2 4 6 …… 2k-2 2k
k k-1 k-2 2 1
如果 n=2kn=2k ，那么如上图所示，第一轮消除完了之后，剩下的数字就是第二排的偶数部分。
接着就要从右往左递归地消除了，那我们从右往左给绿色数字重新编号为 1 到 k，问题就转化为了 k 个数字的情况下，最后剩余的数字是几了。

假设我们用 f(2k)表示初始时 n=2k个数字最后剩下的编号，那么第二排重新编号后最后剩下的数字就是 f(k) ,第二排数字整除 2 ，再加上第三排的编号，结果一定等于 k+1 。所以我们就得到了公式：
f(2k) = 2(k+1-f(k))
比如说当 f(k) = 2 时,那他的最初的编号应该就是
f(2k) = 2k -2

当n= 2k +1 时,
f(2k+1)=2(k+1−f(k))
我们统一可知:
f(n)=2(⌊n/2⌋ + 1 −f(⌊n/2⌋))

var lastRemaining = function(n) {
    return n==1 ? 1 : 2*(parseInt(n/2)+1-lastRemaining(parseInt(n/2)));
}

image.png

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/filter-restaurants-by-vegan-friendly-price-and-distance