Codility 数组中的绝对不同计数
我昨天参加了Codility的面试测试，今天得知我没通过，真不幸的是，Codility和雇主都没有告诉我哪里出错了。所以我希望能得到一些帮助，了解我哪里做得不好。我知道Codility非常重视程序运行的速度和在处理大数据时的表现。虽然我没有逐字抄写题目，但我记得大概是这样的：
- 计算数组a中绝对不同的元素数量。这里的“绝对不同”是指如果数组中有-3和3，这两个数字就不算不同，因为|-3|=|3|。我觉得举个例子会更清楚。
比如说，数组a={-5,-3,0,1,-3}，结果应该是4，因为这个数组中有4个绝对不同的元素。
题目还提到数组的长度会小于等于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));
}
}
36 个回答
这里有一个简单的解决方案。
public class test{
public static int dis(Integer[] arr) {
out.println(Arrays.asList(arr));
if (arr.length == 0) {
return 0;
}
int i = 0;
int j = arr.length - 1;
int c = 0;
while (i <= j) {
if ((j != arr.length - 1) && (Math.abs(arr[j]) == Math.abs(arr[j + 1]))) {
out.println("skipping J==" + j);
j--; continue;
}
if ((i != 0) && (Math.abs(arr[i]) == Math.abs(arr[i - 1]))) {
out.println("skipping I==" + i);
i++; continue;
}
if (Math.abs(arr[i]) < Math.abs(arr[j])) {
j--;
c++;
}
else if (Math.abs(arr[i]) > Math.abs(arr[j])) {
i++; c++;
}
else {
i++; j--; c++;
}
out.println("I=" + i + " J=" + j + " C=" + c);
}
return c;
}
public static void main(String[] arg){
//Integer[] a = {34,2,3,4,3,-2,3};
//out.println("distinct elements are" + dis(a));
Integer[] aa={-5,-3,0,1,3};
out.println("distinct elements count " + dis(aa));
Integer[] ab={-5,-3,0,1,3, 4, 6, 7};
out.println("distinct elements count " + dis(ab));
Integer[] ac={-5};
out.println("distinct elements count " + dis(ac));
Integer[] acc={9};
out.println("distinct elements count " + dis(acc));
Integer[] ad={9,9,9};
out.println("distinct elements count " + dis(ad));
Integer[] ae={-5,-5};
out.println("distinct elements count " + dis(ae));
Integer[] aee={1,5,5,5,5};
out.println("distinct elements count " + dis(aee));
Integer[] af={-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8};
out.println("distinct elements count " + dis(af));
}
}
输出结果是
[-5, -3, 0, 1, 3]
distinct elements count 4
[-5, -3, 0, 1, 3, 4, 6, 7]
distinct elements count 7
[-5]
distinct elements count 1
[9]
distinct elements count 1
[9, 9, 9]
distinct elements count 1
[-5, -5]
distinct elements count 1
[1, 5, 5, 5, 5]
distinct elements count 2
[-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8]
distinct elements count 8
你需要注意的是，这个数组是按升序排列的。
假设这里只有正数，或者题目并不是在问绝对不同的数字。
那么你可以通过遍历这个列表来计算数字的数量，如果当前的元素和上一个元素不同，就把计数器加一。（第一个元素也要加1）
如果你明白这个道理，就可以加入绝对不同的限制。比如可以通过使用两个指针来改进算法，一个指针从开头开始，另一个从结尾开始。然后你还需要确保这两个指针是并行工作的，这样它们最终会在0或者绝对最小的数字（正数/负数）相遇。这会让整个过程稍微复杂一些，但这是可行的。
如果数组是排好序的，你可以通过查看相邻的元素来找到重复的值。为了比较绝对值，你需要从数组的两头开始，这样可以避免创建新的数据结构。
补充说明：在我看来，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;
}
打印结果
对于1亿个数字，使用数组平均耗时279,623微秒，使用Set平均耗时1,270,029微秒，比例为4.5。
对于1000万个数字，使用数组平均耗时28,525微秒，使用Set平均耗时126,591微秒，比例为4.4。
对于100万个数字，使用数组平均耗时2,846微秒，使用Set平均耗时12,131微秒，比例为4.3。
对于10万个数字，使用数组平均耗时297微秒，使用Set平均耗时1,239微秒，比例为4.2。
对于1万个数字，使用数组平均耗时42微秒，使用Set平均耗时156微秒，比例为3.7。
对于1000个数字，使用数组平均耗时8微秒，使用Set平均耗时30微秒，比例为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, 508, 478, 440, 410, 373, 343, 305, 275, 239, 205, 171, 137, 102, 68, 34, 0]
这些值是倒序的，因为HashMap生成了一个链表。