首页 > 代码库 > 45、圆圈中最后剩下的数字

45、圆圈中最后剩下的数字

2024-10-15 01:19:02   212人阅读

思路1：环形链表，每次只删除一个数，都从第0个开始。每次都从链表重复遍历，每删除一个，走m步，共n遍

时间O（nm),空间o(n)

 

技术分享 
import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n < 1 || m < 1) {
            return -1;
        }
        List<Integer> list =  new LinkedList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int idx = 0;
        while(list.size() > 1) {
            // 只要移动m-1次就可以移动到下一个要删除的元素上
            for (int i = 1; i < m; i++) {
                idx = (idx + 1) % list.size();//保证删除后，当数组数量小于m时，仍能正确的去删除
            }
            list.remove(idx);
        }
        
        return  list.get(0);
    }
    
}
View Code

 

 

思路2：时间O（n）,空间o（1），

f（n,m） = f ‘(n - 1, m) {删除一个数后，再每次去删除第m个，最后剩下的数  ，一定等于， 上一次操作中，再每次去删除第m个，最后剩下的数}

即，不管处于第几次删除第m个数的循环里，最后剩下的数是一样的。

f(n,m) = {0,n=1（f(n,m)表示在n个数中，每次删除第m个后，最后剩下的一个数）

　　　　[f(n -1,m) + m] % n, n > 1　

 

技术分享 
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
         if (n < 1 || m < 1) {
             return -1;
         }
        int last = 0;      
        for (int i = 2; i <= n; i++) {
            last = (last + m) % i;        
        } 
        return last;
    }
}
View Code

 

45、圆圈中最后剩下的数字


联系
我们