（华为笔试）删数约瑟夫环问题

╰半橙微兮° 2022-07-16 04:18 108阅读 0赞

删数

*  热度指数：2641时间限制：1秒空间限制：32768K
 *  本题知识点： [模拟][Link 1]
 *  [ 算法知识视频讲解][Link 2]

## 题目描述 ##

有一个数组a\[N\]顺序存放0~N-1，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。以8个数(N=7)为例:｛0，1，2，3，4，5，6，7｝，0->1->2(删除)->3->4->5(删除)->6->7->0(删除),如此循环直到最后一个数被删除。

##### 输入描述: #####

每组数据为一行一个整数n(小于等于1000)，为数组成员数,如果大于1000，则对a[999]进行计算。

##### 输出描述: #####

一行输出最后一个被删掉的数的原始下标位置。

##### 输入例子: #####

##### 输出例子: #####

## 约瑟夫环问题 ##

0,1,2,..., n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第K个数字。（对于上述此题，m=3，因为每隔2个，所以删除第三个），求圆圈里最后剩下的一个数字。

在这n个数字中，第一个被删除的数字是（K-1）%n.

那么第一次被淘汰的人编号一定是K-1(假设K < n，若K > n则为(K-1) mod n)。将被选中的人标记为”\#”：

0 1 2 3 … K-2 \# K K+1 K+2 … n-1

第二轮报数时，起点为K这个候选人。并且只剩下n-1个选手。假如此时把k看作0’，k+1看作1’… ，对应如下

0     1 2 3 ... K-2  # K  K+1 K+2 ... n-1
    n-K'             n-2'   0'  1'  2' ... n-K-1'

此时在0’,1’,…,n-2’上再进行一次K报数的选择。而f\[n-1\]的值已经求得，因此我们可以直接求得当选者的编号s’。  
但是，该编号s’是在n-1个候选人报数时的编号，并不等于n个人时的编号，所以我们还需要将s’转换为对应的s。  
通过观察，s和s’编号相对偏移了K，又因为是在环中，因此得到s = (s'+K) mod n。  
即f\[n\] = (f\[n-1\] + k) mod n。

如果最后剩下1个人，则一定是删除第0个。得到f\[1\]=0。最后得到地推公式：

f[1] = 0 
    f[n] = (f[n - 1] + K) mod n

时间复杂度为O(N),空间复杂度为O(1)。

下面是基于循环实现代码：

int remainingLast(int n,int k) {
    			int last=0;
    			for(int i=2;i<=n;i++) {
    				last=(last+k)%i;
    			}
    			return last;
    		}

针对上面的删数问题，得如下解法：

import java.util.*;
     
    public class Main {
            public static void main(String[] args){
                Scanner in = new Scanner(System.in);
                while(in.hasNext()){
                    int n=in.nextInt();
                    System.out.println(remainingLast(n,3));
                }
            }
         
            private static int remainingLast(int n,int k) {
                int last=0;
                for(int i=2;i<=n;i++)
                    last=(last+k)%i;
                return last;
            }
    }

[Link 1]: http://www.nowcoder.com/questionCenter?questionTypes=000100&mutiTagIds=595
[Link 2]: http://www.nowcoder.com/courses/1