约瑟夫环

2017-08-12  本文已影响0人  博客的博客

解法一

用一个list模拟删除过程

   public static int josephRing(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        List<Integer> array = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            array.add(i);
        }
        int step = 0;
        while (array.size() > 1) {
            step += m;
            step = (step) % array.size() - 1;
            if (step < 0) {
                array.remove(array.size() - 1);
                step = 0;
            } else {
                array.remove(step);
            }
        }
        return array.get(0);
    }

解法二

数学公式,推到过程还没看懂

    public static int josephRing2(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;
    }
上一篇 下一篇

猜你喜欢

热点阅读