yah*_*ahh 11 c# c++ python java algorithm
所以我昨天接受了抄袭面试,并且今天被告知我失败了,不幸的是,我没有给出任何其他信息,无论是鳕鱼还是雇主都知道我搞砸了哪里,所以我会感谢一些帮助,知道我哪里出错了.我知道codility非常重视程序运行的速度以及它对大数字的行为方式.现在我没有复制粘贴问题所以这是我记得的大约
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));
}
}
如果数组已排序,您可以通过查看neightbours找到重复项.比较绝对值需要从开始和结束开始.这样可以避免创建新结构.
编辑:恕我直言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个,使用Set平均花费1,270,029个,比率= 4.5
对于10,000,000个数字,使用数组平均花费28,525 us,使用Set平均花费126,591 us,比率= 4.4
对于1,000,000个数字,使用数组平均花费2,846个,使用Set平均花费12,131个,比率= 4.3
对于100,000个数字,使用数组平均花费297 us,使用Set平均花费1,239 us,比率= 4.2
对于10,000个数字,使用数组平均花费42 us,使用Set平均花费156 us,比率= 3.7
对于1,000个数字,使用数组平均花费8 us,使用Set平均花费30 us,比率= 3.6
在@Kevin K的观点上,即使Integer的哈希值是唯一的,它甚至可以发生冲突,它可以映射到容量受限的同一个桶.
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已生成LinkedList.
您应该注意数组按升序排序的事实.
让我们假设只有正数,或者问题不是绝对不同的.
如果实际元素与最后一个元素不同,您可以通过迭代列表来计算数字,并将计数器递增1.(和第一个元素+1)
如果您了解这一点,则可以添加绝对不同的约束.例如,通过两个指针改进算法,一个从开始开始,一个从结束开始.然后你还要注意两个指针的工作方式是并行的,这样两个指针都会以0或absoulte最低数字(正/负)结束 - 这会使整个东西复杂化一些,但这是可能的.