045-圆圈中最后剩下的数字.md

面试题45 圆圈中最后剩下的数字

题目：

0, 1, 2, ..., n-1 这 n 个数字排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。 求出这个圆圈里剩下的最后一个数字。

package algorithm.foroffer.top50;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * description:
 *
 * @author liyazhou
 * @create 2017-06-03 20:41
 * 面试题 46：圆圈中最后剩下的数字
 *
 * 题目：
 *      0, 1, 2, ..., n-1 这 n 个数字排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。
 *      求出这个圆圈里剩下的最后一个数字。
 *
 * 考查点：
 *      1. 约瑟夫环问题
 *
 * 思路：
 *      1. 圆形链表
 *
 *
 */
public class Test45 {

    public int lastRemainElement(int n, int m){
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i ++) list.add(i);

        int idx = 0;
        for (int i = 0; i < n-1; i ++){
            // for (int j = 0; j < m-1; j ++) idx ++;
            idx = idx + (m-1);
            idx = idx % list.size();
            list.remove(idx);
        }
        return list.get(0);
    }

    @Test
    public void test(){
        System.out.println(lastRemainElement(5, 3));
    }


}

使用数组求解 2017-8-17 21:30:30

 public int LastRemaining_Solution0(int n, int m) {
     if (n == 0 || m == 0) return -1;
     
     int[] arr = new int[n];  // 下标表示id
     int num = 0;  // 当前报数
     int idx = 0;  // 当前报数的id
     int counter = 0;  // 已经被删除的个数
     
     for (int i = 0; ; i ++){
         num = i % m;
         // idx = idx % n;
         if (num == m-1) {
             arr[idx] = -1;
             counter ++;
             if (counter == n-1) break;
         }
         
         
         // 查找下一个报数的id
         idx ++;
         if (idx == n) idx = 0;
         while (arr[idx] == -1){
             idx ++;
             if (idx == n) idx = 0;
         }

     }
     
     
     for (int j = 0; j < arr.length; j ++){
         if (arr[j] == 0) return j;
     }
     
     return -1;
 }