求解圆圈中最后剩下的数字

简介:

一,问题描述

将 0,1,2....n-1 一共n个数字排成一个圆圈。从数字0开始每次从这个圆圈里面删除第m个数字( 1=<m<=n, 比如第1个数字为0)。求出这个圆圈里面最后剩下的那个数字。

 

二,问题分析

使用java.util.LinkedList类保存这N个数字,并调用 remove(int index)方法来执行删除链表中指定位置的元素。

问题的关键是:如何找到链表中 每次待删除的元素的位置。一共有下面三种方法:

第一种方式是对链表进行遍历,第二种方式是模拟链表的遍历(但是不对链表进行真正的遍历),第三种方式是:直接用公式(这其实是一个约瑟夫环问题,有现成的公式来求解)。

本文记录第二种方法的实现。

 

三,代码分析

复制代码
 1     public int lastNumber(int[] arr, int m){
 2         if(arr == null || arr.length == 0 || m <= 0 || m > arr.length)
 3             throw new IllegalArgumentException();// illegal arguments
 4         
 5         LinkedList<Integer> cirList = new LinkedList<>(); 6         //init
 7         for (int ele : arr) {
 8             cirList.add(ele);
 9         }
10         
11         int nextPosition = m - 1;
12         while(cirList.size() > 1)
13         {
14             cirList.remove(nextPosition);
15             nextPosition = nextIndex(cirList, nextPosition, m);
16         }
17         return cirList.get(0);
18     }
复制代码

1)第2-3行,检测参数是否合法。第7-8行进行初始化:即将所有的元素添加到链表中,这表明程序的空间复杂度为O(N)

2)第11行表示当前待删除的元素 在 链表中的位置。初始时为m-1,表示删除链表中的第 m 个元素。(因为链表下标是从0开始的嘛)

3)12行while循环,当链表中的元素个数还是大于1时,表示:还要继续删除。第14行删除第m个元素,第15行获取下一个待删除的元素(从题意上理解:还是环中的“第m个”元素)

 

那问题的关键是:如何获取下一个元素?当删除了一个元素后,链表的长度是变了的(减少了1),而且始终要将链表视为一个”环“,这样第 m 个元素才有意义(尤其是 m 大于 当前链表中的元素个数的时候)。

 

复制代码
 1 private int nextIndex(LinkedList<Integer> cirList, int currentPosition, int m){
 2         int next = -1;//下一个待删除的元素索引
 3         if(currentPosition >= cirList.size())//当已删除的结点刚好是链表中的最后一个结点
 4             currentPosition = 0;
 5         int len = cirList.size();
 6         int last = len - currentPosition;//链表中后面还可以移动的节点个数
 7         if(last < m)//链表中后面还可以移动的节点个数 小于 m 时,需要返回到表头去
 8         {
 9             int remain = m - last;
10             //再从表头移动 remain个元素
11             
12             //如果需要跳过的元素个数 大于 链表中已有的元素个数
13             while(remain > len){
14                 remain = remain - len;
15             }
16             next = remain - 1;//substract 1 because index start from zero
17         }else{
18             next = currentPosition + m - 1;
19         }
20         return next;
21     }
复制代码

实现“获取下一个待删除的元素索引” 的总体思路是:根据上一次删除链表中的元素的索引,求出从该索引到链表的表尾有多少个元素? 这是第6行代码的功能。

然后第7行if语句判断,后面还可以移动的元素个数是否小于m,若小于m,说明还需要再返回到表头去,再跳过若干个元素才是环中的第m个元素。

当然,求解下一个待删除的元素可能有一些细节问题:比如第 13-14行,它描述的情景是:m很大,经过若干次删除之后,当前链表中的元素很少 的情况。

 

四,完整代码实现---(只测试了部分 测试用例,不保证完全正确)

复制代码
import java.util.LinkedList;

public class LastNumberInCircle {
    
    public int lastNumber(int[] arr, int m){
        if(arr == null || arr.length == 0 || m <= 0 || m > arr.length)
            throw new IllegalArgumentException();// illegal arguments
        
        LinkedList<Integer> cirList = new LinkedList<>();//模拟一个环形链表
        //init
        for (int ele : arr) {
            cirList.add(ele);
        }
        
        int nextPosition = m - 1;
        while(cirList.size() > 1)
        {
            cirList.remove(nextPosition);
            nextPosition = nextIndex(cirList, nextPosition, m);
        }
        return cirList.get(0);
    }
    
    private int nextIndex(LinkedList<Integer> cirList, int currentPosition, int m){
        int next = -1;//下一个待删除的元素索引
        if(currentPosition >= cirList.size())//当已删除的结点刚好是链表中的最后一个结点
            currentPosition = 0;
        int len = cirList.size();
        int last = len - currentPosition;//链表中后面还可以移动的节点个数
        if(last < m)//链表中后面还可以移动的节点个数 小于 m 时,需要返回到表头去
        {
            int remain = m - last;
            //再从表头移动 remain个元素
            
            //如果需要跳过的元素个数 大于 链表中已有的元素个数
            while(remain > len){
                remain = remain - len;
            }
            next = remain - 1;//substract 1 because index start from zero
        }else{
            next = currentPosition + m - 1;
        }
        return next;
    }
    
    //hapjin test
    public static void main(String[] args) {
        LastNumberInCircle obj = new LastNumberInCircle();
        int len = 5;
        int m = 3;
        int[] arr = new int[len];
        for(int i = 0; i < len; i++)//init
            arr[i] = i;
        assert len >= m;
        int last = obj.lastNumber(arr, m);
        System.out.println(last);
    }

本文转自hapjin博客园博客,原文链接:http://www.cnblogs.com/hapjin/,如需转载请自行联系原作者
}
复制代码

 

相关文章
|
4天前
|
弹性计算 人工智能 安全
云上十五年——「弹性计算十五周年」系列客户故事(第二期)
阿里云弹性计算十五年深耕,以第九代ECS g9i实例引领算力革新。携手海尔三翼鸟、小鹏汽车、微帧科技等企业,实现性能跃升与成本优化,赋能AI、物联网、智能驾驶等前沿场景,共绘云端增长新图景。
|
10天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
2天前
|
云安全 人工智能 安全
Dify平台集成阿里云AI安全护栏,构建AI Runtime安全防线
阿里云 AI 安全护栏加入Dify平台,打造可信赖的 AI
|
9天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
5天前
|
人工智能 运维 Java
Spring AI Alibaba Admin 开源!以数据为中心的 Agent 开发平台
Spring AI Alibaba Admin 正式发布!一站式实现 Prompt 管理、动态热更新、评测集构建、自动化评估与全链路可观测,助力企业高效构建可信赖的 AI Agent 应用。开源共建,现已上线!
471 12
|
3天前
|
编解码 文字识别 算法
一张图能装下“千言万语”?DeepSeek-OCR 用视觉压缩长文本,效率提升10倍!
一张图能装下“千言万语”?DeepSeek-OCR 用视觉压缩长文本,效率提升10倍!
363 10
|
10天前
|
编解码 自然语言处理 文字识别
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
凌晨,Qwen3-VL系列再添新成员——Dense架构的Qwen3-VL-8B、Qwen3-VL-4B 模型,本地部署友好,并完整保留了Qwen3-VL的全部表现,评测指标表现优秀。
678 7
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
|
12天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
805 2