【杂题】剑指 Offer 62. 圆圈中最后剩下的数字-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月20日上午11:17

链表解法更容易懂一些

class Solution {
    public int lastRemaining(int n, int m) {
        // int x = 0;
        // for(int i = 2; i <= n; i++){
        //     x = (x + m) % i;
        // }
        // return x;

        //链表解法
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++){
            list.add(i);
        }
        int index = 0;
        while(n > 1){
            index = (index + m - 1) % n;
            list.remove(index);
            n--;
        }
        return list.get(0);
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月18日上午1:05

数学公式，只会背过…..

class Solution {
    public int lastRemaining(int n, int m) {
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
}

0 赞同 0 条回复

T 普通 2022年12月3日上午10:08

模拟链表

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

0 赞同 0 条回复

symbol 普通 2022年12月3日上午8:04

//递归解法

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

//迭代解法
func lastRemaining(n int, m int) int {
    dp := 0 //题目从数字零开始
    for i := 2; i <= n; i++ {
        dp = (dp + m) % i
    }
    return dp
}

0 赞同 0 条回复

你有点可爱喔普通 2022年12月2日下午4:55

    class Solution {
        public int lastRemaining(int n, int m) {
//f(n,m)和 f(n-1,m)之间的关系
            if (n == 0) return n;
            int res = 0;
            for (int i = 1; i <= n; i++) {
                res = (res + m) % i;
            }
            return res;
        }
    }

0 赞同 0 条回复

青木普通 2022年12月1日下午11:32

/** 
    推导好难看懂T_T
    题解的意思应该是根据归纳法，(f(n-1) + m%n) % n = f(n)
    所以只要知道f1的值就可以推导，而f1的答案恒为0

 */

class Solution {
    public int lastRemaining(int n, int m) {
        int x = 0;
        for(int i=2; i<=n; i++){
            x = (x+m) % i;
        }
        return x;

        // 硬来
        // int[] num = new int[n];
        // for(int i=0; i<n; i++) num[i] = i;

        // int cnt = 0, pos = -1;

        // while(n > 5){
        //     cnt = 0;
        //     while(cnt != m){
        //         pos = (pos + 1) % n;
        //         if(num[pos] != -1){
        //             cnt++;
        //         }
        //     }
        //     num[pos] = -1;
        //     n--;
        // }
        // for(int i=0; i<num.length; i++) {
        //     if(num[i] != -1) {
        //         return num[i];
        //     }
        // }
        // return n;
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年12月1日上午10:52

时间复杂度O(N^2)空间复杂度O(N)

/**
用list模拟的好处在于可以动态的更新数组长度，下标对应变化
 */
class Solution {
    public int lastRemaining(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0;i < n;i++) {
            list.add(i);
        }
        int idx = 0;
        while(n > 1) {
            idx = (idx + m - 1) % n;
            list.remove(idx);
            n--;
        }
        return list.get(0);
    }
}

注意：如果使用LinkedList会超时，LinkedLIst删除指定节点的时间复杂度为O(1),但是在remove的时间复杂度仍然是O(n),因为需要从头遍历到需要删除的位置。

ArrayList索引到需要删除的位置为O(1)，但是删除是O(N)

ArrayList 的 remove 操作在后续移位的时候，其实是内存连续空间的拷贝的！所以相比于LinkedList大量非连续性地址访问，ArrayList的性能是很好的

每次删除的时间复杂度是 O(n)，删除了 n-1 次，所以整体时间复杂度是 O(n^2)

数学解法

时间复杂度O(N)

这么著名的约瑟夫环问题，是有数学解法的！
因为数据是放在数组里，所以我在数组后面加上了数组的复制，以体现是环状的。我们先忽略图片里的箭头：

” alt=”image.png” />

图中的绿色的线指的是新的一轮的开头是怎么指定的，每次都是固定地向前移位 m个位置。

然后我们从最后剩下的 3 倒着看，我们可以反向推出这个数字在之前每个轮次的位置。

最后的3下标是0

第四轮反推，补上m个位置，然后模上当时的数组大小2，位置是(0+3)%2=1

第三轮(1+3)%3=1

第二轮(1+3)%4=0

第一轮(0+3)%5=3

所以最终剩下的数字的下标就是3。因为数组是从0开始的，所以最终的答案就是3。

总结一下反推的过程，就是 (当前index + m) % 上一轮剩余数字的个数。

假设我们最好剩余的数字是N。

执行完“删除第三个元素”的操作后，N在新数组中的位置P的意义是什么？ ——它表示，在新数组中，N前面有还有P个元素。那么，在当前数组中，N前面一定有“P+3”个元素。明白了这一点即可开始倒推。

最后一轮：当前有1个元素。N的位置是0；

倒数第2轮：当前有2个元素。已知在执行完“删除第三个元素”后，N在新数组中的位置是0。则说明在本轮中N前面有0+3=3个元素，所以N的位置是3，然而本轮只有2个元素，所以N的实际位置是（0+3）%2=1；

倒数第3轮：当前有3个元素。已知在执行完“删除第三个元素”后，N’在新数组中的位置是1。说明此刻，N前面有1+3=4个元素，所以N的位置是4。而当前数组只有3个元素，故实际位置是（1+3）%3=1；

/**
当前轮的下标=(上一轮的下标+偏移位数)%上一轮的个数
 */
class Solution {
    public int lastRemaining(int n, int m) {
        int idx = 0;
        for(int i = 2; i <= n;i++) {
            idx = (idx + m) % i;
        }
        return idx;
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月30日下午10:38

时间复杂度O（n），空间复杂度O（1）

class Solution {
    public int lastRemaining(int n, int m) {

        int res = 0;
        for(int i=1;i<=n;i++){
            res = (res+m)%i;
        }
        return res;
    }
}

0 赞同 0 条回复

Mooby 普通 2022年11月30日下午10:15

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
    public int lastRemaining(int n, int m) {
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:36

class Solution {
public:
    int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) { //过于离谱，dp
            x = (x + m) % i;
        }
        return x;
    }
};

0 赞同 0 条回复

【杂题】剑指 Offer 62. 圆圈中最后剩下的数字

共以下 10 个回答

数学公式，只会背过…..

# 回答此问题取消回复

【杂题】剑指 Offer 62. 圆圈中最后剩下的数字

共以下 10 个回答

数学公式，只会背过…..

# 回答此问题 取消回复

# 回答此问题取消回复