资讯专栏INFORMATION COLUMN

[Java] 关于一道面试题的思考

rozbo / 495人阅读

摘要:对于这种会退出的情况,数组显然不能像链表一样直接断开,因此采用标记法先生成一个长度为的布尔型数组,用填充。中对整个进行遍历才能得到此时数组中的数量。

文中的速度测试部分,时间是通过简单的 System.currentTimeMillis() 计算得到的,
又由于 Java 的特性,每次测试的结果都不一定相同,
对于低数量级的情况有 ± 20 的浮动,对于高数量级的情况有的能有 ± 1000 的浮动。

这道题本质上是个约瑟夫环问题,最佳解法在最下面,本文只是探究一下数组暴力和链表的表现差异。
题目

N 个人围成一圈,顺序排号。从第一个人开始报数(从1数到3),凡是到3的人退出圈子,问最后留下的是原来第几号。

样例

2 个人时留下的是第二个;

3个人时留下的是第二个;

5个人时留下的是第四个;

12个人时留下的是第十个;

100,000个人时留下的是第92620个人。

机器环境

CPU Intel Xeon E3-1231 v3 @ 3.40GHz

RAM 16 GB

暴力解决

虽然第一反应是用链表,但对于人数在1000以下的量级感觉数组也足以胜任,因此先用数组试试。

对于这种会 退出 的情况,数组显然不能像链表一样直接断开,因此采用标记法:

先生成一个长度为 N 的布尔型数组,用 true 填充。

报号时,对于报到 3 的位置,用 false 来标记该位置,下次循环如果遇到 false 则可以直接跳过。

那么等到数组内只剩一个 true 的时候,找到其位置,即是最后留下来的人的位置。

既然暴力,那干脆彻底一点:

    public static int findIndex(final int N) {
        boolean[] map = new boolean[N];
        Arrays.fill(map, true);
        int walk = 1;
         // 因为是站成一个圆,所以在遍历到最后时需要将下标重新指向 0
           // count(map) 就是遍历整个数组计算还剩余的 true 的数量
        for (int index = 0; count(map) > 1; index = (index == N - 1) ? 0 : (index + 1)) {
            // 对于 false 可以直接跳过,因为它们相当于不存在
               if (! map[index]) continue;
             // 报号时如果不是3 则继续找下一位;
            if (walk++ != 3) continue;
             // 如果是 3,则重置报号,并将当前位置的值改为 false
            walk = 1;
            map[index] = false;
        }
        return find(map);
    }
    
    // 因为是 count(map) == 1 的情况下才会调用这个方法,所以直接返回第一个 true 所在的位置即可
    public static int find(boolean[] map) {
        for (int i = 0; i < map.length; i++) {
            if (!map[i]) continue;
            return i + 1;
        }
        return -1;
    }

    public static int count(boolean[] map) {
        int count = 0;
        for (boolean bool : map) {
            count += bool ? 1 : 0;
        }
        return count;
    };

对于这个解法,可以跑一下测试看看耗时:

N time / ms
100 1
1,000 13
10,000 686
100,000 80554

很显然,这种暴力的做法对于大一点的数量级就很吃力了,但是我又不想那么快就用链表,有没有哪里是可以优化的呢。

消除循环

其实在前面的解法中,耗时操作有这么几个:

findIndex 中不停得对整个 map 进行遍历,即便对于 false 直接跳过,但杯水车薪。

count 中对整个 map 进行遍历才能得到此时数组中 true 的数量。

find 中同样需要对整个 map 进行遍历才能得到剩下的一个 true 的下标。

其中第一点应该是这种解法的本质,没什么好办法,那么看看后两点。

消除 count

这个方法想做的事就是每次循环时检查此时数组中 true 的数量是不是只剩一个了,因为这是循环的终结条件。

那么我们可以引入一个计数器:

    private static int findIndex(final int N) {
        boolean[] map = new boolean[N];
        Arrays.fill(map, true);
        int walk = 1;
         int countDown = N;
        for (int index = 0; countDown > 1; index = (index == N - 1) ? 0 : (index + 1)) {
            if (! map[index]) continue;
            if (walk++ != 3) continue;
            walk = 1;
            map[index] = false;
               countDown -= 1;
        }
        return find(map);
    }

改成这种做法后,猜猜对于 100,000 这个数量级,这个暴力算法需要用时多久呢?

答案是 11 ms

对于 100,000,000 这个数量级,这个暴力算法仍只需要 3165 ms

稍稍透露一下,后边的链表解法在这个数量级的成绩是 7738 ms,当然可能是我太垃圾了,发挥不出链表的威力 Orz)

消除 find

这个方法要做的是从整个数组中找到唯一的 true 的下标,这同样可以用一个外部变量来消除循环:

    private static int findIndex(final int N) {
        boolean[] map = new boolean[N];
        Arrays.fill(map, true);
        int walk = 1;
         // 记录现在访问到值为 true 的下标
        int current = 0;
        int countDown = N;
        for (int index = 0; countDown > 1; index = (index == N - 1) ? 0 : (index + 1)) {
            if (! map[index]) continue;
            if (walk++ != 3) {
                   // 记录最后一次遇到 true 的位置
                current = index;
                continue;
            }
            walk = 1;
            map[index] = false;
            countDown -= 1;
        }
         // 人的位置是从 1 开始数的,所以这里要加 1
        return current + 1;
    }

但是这个改动对速度的提升效果很小,对于 100,000,000 这个数量级,速度仍然在 3158 ~ 3191 ms 左右。

不暴力了,用链表吧

使用链表可以很方便得体现 退出 这个概念,链表的长度会随着算法的进行而越来越短直至剩下最后一个元素。因为没有 跳过标记为 false 的步骤,理论上会比暴力数组解法要快。

    static class Node {
           // 当前节点的下标,即人的位置
        int index;
           // 上一个节点
        Node prev;
         // 下一个节点
        Node next;

        public Node (int index) {
            this.index = index;
        }

        public Node append(Node next) {
            this.next = next;
            next.prev = this;
            return next;
        }

         // 需要报号为3的人(当前元素)退出时,从链表中断开并将两边拼接起来
        public Node jump() {
            Node newNode = this.next;
            newNode.prev = this.prev;
            newNode.prev.next = newNode;
            this.prev = null;
            this.next = null;
            return newNode;
        }

        public static int findIndex(final int N) {
            Node root = new Node(1);
               // 初始化链表并赋值,这个过程对于很大的数量级而言速度肯定是慢过对数组的赋值的,
             // 毕竟类的实例化需要开销。因此这段初始化不计入时间
            Node current = root;
            for (int i = 2; i <= N; i++) {
                current = current.append(new Node(i));
            }
            // 将首尾相连构成循环列表
            current = current.append(root);
          
            long mills = System.currentTimeMillis();
          
            int COUNTER = N;
            int walk = 1;
            while (COUNTER > 1) {
                if (walk++ != 3) {
                    current = current.next;
                } else {
                    current = current.jump();
                    walk = 1;
                    COUNTER -= 1;
                }
            }

            System.out.println(System.currentTimeMillis() - mills);
            return current.index;

        }
    }
看看两种解法的速度对比
N 数组暴力法 / ms 数组暴力法(改进) / ms 链表法 / ms
100 2 0 0
1,000 15 1 0
10,000 673 5 1
100,000 79998 10 3
1,000,000 N/A 38 64
10,000,000 N/A 309 718
100,000,000 N/A 3151 7738

​ 对于 1,000,000 及以上的数量级就没测原数组暴力法了,太慢了...

总结

可以看到,在百万级别,改进的数组暴力法已经要比链表法快一半了,在亿级要快的更多。

当然这个速度差异很大程度上是因为随着数量级的加大,链表法所需要的内存开销已经超出一个合理的范围了,随之而来的就是链表的断开重组操作要比 标记 重太多了。

但是这只是 想知道最后一个人的位置 的情况,数组的下标可以做到一定程度的契合,如果情况更复杂了,显然数组就不够用了。

对于链表法在超大数量级的解法,感觉可以用多线程来做一次整体循环内的截断,只是这样复杂度就上去了,暂时不做了,有兴趣的读者可以自行尝试一下。

算法的力量
    public static int josephus(int n) {
        int res = 0;
        if (n == 0) return 0;
        if (n < 3) {
            for (int i = 2; i <= n; i++) {
                res = (res + 3) % i;
            }
        } else {
            res = josephus(n - n / 3);
            if (res < (n % 3)) {
                res = res - (n % 3) + n;
            } else {
                res = res - (n % 3) + (res - (n % 3)) / 2;
            }
        }
        return res;
    }

    public static void main(String ...args) {
        System.out.println(hosephus(1000000000));
    }

这个解法对于一亿这个数量级的运算时间是不到 0 ms,来自我的 ACMer 同学 ( 打不过正规军啊,跪了

据我同学所说:

递归层数 log 级别,n 可以达到 1e18 级别,15 ms 内给出答案。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/68851.html

相关文章

  • 一道【脉脉】上 头条 算法面试题的思考

    摘要:偶然间在脉脉上看到了一道头条的算法面试题按照题目的理解,简单的写了一个网页开始学的不仅是技术,更是梦想得到了如下效果图得到如题可以进行开关的示例在最后一个灯特殊处理,链接第一个灯,形成环经过测试发现只要从序号开始,如 偶然间在脉脉上看到了一道头条的算法面试题 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照题...

    tyheist 评论0 收藏0
  • 一道【脉脉】上 头条 算法面试题的思考

    摘要:偶然间在脉脉上看到了一道头条的算法面试题按照题目的理解,简单的写了一个网页开始学的不仅是技术,更是梦想得到了如下效果图得到如题可以进行开关的示例在最后一个灯特殊处理,链接第一个灯,形成环经过测试发现只要从序号开始,如 偶然间在脉脉上看到了一道头条的算法面试题 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照题...

    xuxueli 评论0 收藏0
  • 尾调用优化——记一道面试题的思考

    摘要:如果函数内部还调用函数,那就还有一个的调用帧,依次类推。等同于等同于如果所有函数都是尾调用,那么完全可以做到每次执行时,调用帧只有一项,这将大大节省内存。这就是尾调用优化。尾递归函数调用自身,称为递归。 前言 面某东,有一道题目是 实现一个斐波拉契数列, 已知第一项为0,第二项为1,第三项为1,后一项是前两项之和,即f(n) = f(n - 1) + f(n -2)。 拿到这个题目,二...

    awkj 评论0 收藏0
  • 链式调用与事件循环--一道JavaScript面试题的思考

    摘要:最后画几张粗糙的图,简单描述一下这个执行的过程因为是链式调用,所以在链上的都会入栈然后执行,额,执行栈少画了和。。。 前言:昨天在群里讨(jin)论(chui)技(niu)术(pi),有位老铁发了一道他面的某公司面试题,顺手保存了。今早花了一点时间把这题做了出来,发现挺有意思的,决定在今天认真工(hua)作(shui)前,与大家分享我的解题方案和思考过程。 题目如下(可以自己先思考一会...

    wow_worktile 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<