codility 数组中的绝对不同计数

Question

所以我昨天参加了 codility 面试测试，今天被告知我失败了，不幸的是，无论是 codility 还是雇主都没有向我提供任何其他信息，说明我在哪里搞砸了，所以如果我知道我哪里出错了，我将不胜感激。我知道 codility 非常重视程序运行的速度以及它对大量数据的行为方式。现在我没有复制粘贴问题所以这是我记得的大约

1. 计算数组 a 中绝对不同的元素的数量，这意味着如果数组中有 -3 和 3，这些数字不是不同的，因为|-3|=|3|。我认为一个例子会更好地清除它

a={-5,-3,0,1,-3} 结果将为 4，因为此数组中有 4 个绝对不同的元素。

该问题还指出a.length将<= 10000，最重要的是它指出假设 数组按升序排序， 但我真的不明白为什么我们需要对它进行排序

如果您认为我错过了一些问题，我会尝试进一步澄清问题。

这是我的代码

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class test2 {

    int test(int[] a){
        Set<Integer> s=new HashSet<Integer>();

        for(int i=0;i<a.length;i++){
            s.add(Math.abs(a[i]));

        }
        return s.size();

    }

    public static void main(String[] args) {
        test2 t=new test2();
        int[] a={1,1,1,2,-1};
        System.out.println(t.test(a));

    }

}

原文由 yahh 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

如果数组已排序，您可以通过查看邻居来找到重复项。要比较绝对值需要从开始和结束开始。这避免了创建新结构。

编辑：恕我直言，HashMap/HashSet 由于冲突而为 O(log(log(n))，如果有完美的散列函数，则只有 O(1)。我原以为不会创建更快但似乎在我的机器上速度只有 4 倍。

综上所述，您可以看到使用 Set 更简单、更清晰、更易于维护。它仍然非常快，并且在 98% 的情况下将是最佳解决方案。

 public static void main(String[] args) throws Exception {
    for (int len : new int[]{100 * 1000 * 1000, 10 * 1000 * 1000, 1000 * 1000, 100 * 1000, 10 * 1000, 1000}) {
        int[] nums = new int[len];
        for (int i = 0; i < len; i++)
            nums[i] = (int) (Math.random() * (Math.random() * 2001 - 1000));
        Arrays.sort(nums);

        long timeArray = 0;
        long timeSet = 0;
        int runs = len > 1000 * 1000 ? 10 : len >= 100 * 1000 ? 100 : 1000;
        for (int i = 0; i < runs; i++) {
            long time1 = System.nanoTime();
            int count = countDistinct(nums);
            long time2 = System.nanoTime();
            int count2 = countDistinctUsingSet(nums);
            long time3 = System.nanoTime();
            timeArray += time2 - time1;
            timeSet += time3 - time2;
            assert count == count2;
        }
        System.out.printf("For %,d numbers, using an array took %,d us on average, using a Set took %,d us on average, ratio=%.1f%n",
                len, timeArray / 1000 / runs, timeSet / 1000 / runs, 1.0 * timeSet / timeArray);
    }
}

private static int countDistinct(int[] nums) {
    int lastLeft = Math.abs(nums[0]);
    int lastRight = Math.abs(nums[nums.length - 1]);
    int count = 0;
    for (int a = 1, b = nums.length - 2; a <= b;) {
        int left = Math.abs(nums[a]);
        int right = Math.abs(nums[b]);
        if (left == lastLeft) {
            a++;
            lastLeft = left;
        } else if (right == lastRight) {
            b--;
            lastRight = right;
        } else if (lastLeft == lastRight) {
            a++;
            b--;
            lastLeft = left;
            lastRight = right;
            count++;
        } else if (lastLeft > lastRight) {
            count++;
            a++;
            lastLeft = left;
        } else {
            count++;
            b--;
            lastRight = right;
        }
    }
    count += (lastLeft == lastRight ? 1 : 2);
    return count;
}

private static int countDistinctUsingSet(int[] nums) {
    Set<Integer> s = new HashSet<Integer>();
    for (int n : nums)
        s.add(Math.abs(n));
    int count = s.size();
    return count;
}

印刷

对于 100,000,000 个数字，使用数组平均需要 279,623 us，使用 Set 平均需要 1,270,029 us，ratio=4.5

对于 10,000,000 个数字，使用数组平均需要 28,525 us，使用 Set 平均需要 126,591 us，ratio=4.4

对于 1,000,000 个数字，使用数组平均需要 2,846 us，使用 Set 平均需要 12,131 us，ratio=4.3

对于 100,000 个数字，使用数组平均需要 297 us，使用 Set 平均需要 1,239 us，ratio=4.2

对于 10,000 个数字，使用数组平均需要 42 us，使用 Set 平均需要 156 us，ratio=3.7

对于 1,000 个数字，使用数组平均需要 8 us，使用 Set 平均需要 30 us，ratio=3.6

---

在@Kevin K的观点上，即使整数也可能发生冲突，即使它的哈希值是唯一的，它可以映射到同一个桶，因为容量是有限的。

 public static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

public static void main(String[] args) throws Exception {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(32, 2.0f);
    for (int i = 0; i < 10000 && map.size() < 32 * 2; i++) {
        if (hash(i) % 32 == 0)
            map.put(i, i);
    }
    System.out.println(map.keySet());
}

印刷

[2032, 2002, 1972, 1942, 1913, 1883, 1853, 1823, 1763, 1729, 1703, 1669, 1642, 1608, 1582, 1548, 1524, 1494, 1456, 1426, 1405, 1375, 1337, 1307, 1255 , 1221, 1187, 1153, 1134, 1100, 1066, 1032, 1016, 986, 956, 926, 881, 851, 821, 791, 747, 713, 687, 653, 610, 576, 550, 516, 47 , 440, 410, 373, 343, 305, 275, 239, 205, 171, 137, 102, 68, 34, 0]

这些值的顺序相反，因为 HashMap 已生成为 LinkedList。

原文由 Peter Lawrey 发布，翻译遵循 CC BY-SA 3.0 许可协议