广联达 7月29第二题

做这道题的心路历程:

1、模拟操作,一个boolean 一次遍历如果没有操作退出 时间复杂度  最好O(n) 最差O(n*n)

2、用set来防止重复,后面想到要取到索引,上了map   ac
private static void compact(int[] arr) {
        // value , index  存值的位置,方便索引 因为不允许有重复的值
        Map<Integer, Integer> map = new HashMap<>();
        // 这个for里面还可以缩减代码,笔试时没想那么多,按照思路写   缩减看下面
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                arr[map.get(arr[i])] = -1;
                map.remove(arr[i]);
                arr[i] = 2 * arr[i];
                while (map.containsKey(arr[i])) {
                    arr[map.get(arr[i])] = -1;
                    map.remove(arr[i]);
                    arr[i] = 2 * arr[i];
                }
                map.put(arr[i], i);
            } else {
                map.put(arr[i], i);
            }
        }
        for (int num : arr) {
            if (num != -1) {
                System.out.print(num + " ");
            }
        }
    }

    // 如果缩减代码
      for (int i = 0; i < arr.length; i++) {
          while (map.containsKey(arr[i])) {
              arr[map.get(arr[i])] = -1;
              map.remove(arr[i]);
              arr[i] = 2 * arr[i];
          }
          map.put(arr[i], i);
     }

完整的整理在我语雀:https://www.yuque.com/zecheng-mchar/crq9nd/wzm9sa#NJHbz

#笔试题目##广联达#
全部评论

相关推荐

叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
评论
7
4
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务