您将获得一个32位无符号整数数组,其长度最大为2 32,其中包含数组中一半以上条目的属性等于N,对于某些32位无符号整数N.查找N查看每个数字在数组中只使用一次并使用最多2 kB的内存.
您的解决方案必须是确定性的,并保证找到N.
这个问题询问如何确定列表中的每个元素是否相同.我如何以合理有效的方式确定列表中95%的元素是否相同？例如:
>>> ninety_five_same([1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1])
True
>>> ninety_five_same([1,1,1,1,1,1,2,1]) # only 80% the same
False
这需要有些效率,因为列表可能非常大.
我想设计一种算法,确定数组A是否为复数,并返回该元素.
如果阵列中的一半以上与x相同,则阵列中存在元素x时,数组为多个.
我想知道是否有一个更有效的分而治之算法运行比我现在的更好.
Assume you have the array
aaabbcac
我将递归分割数组,直到我得到大小为2的子数组,如下所示.
aa ab bc ac
从这里开始,我将比较SUBARRAY中的每个元素以查看它们是否相等:如果是EQUAL,则返回元素,Else,返回false.
aa ab bc ac
a f f f
所以现在我有一个元素A和3的数组.
我正在考虑将它们组合起来:
a f f f
a f <----- combining a and f will give a
a <----- returns a
但是,如果我们查看数组,我们有4个A,它不符合复数数组的标准.如果数组不是复数数组,它应该返回false.
我相信我的算法将在O(n lgn)中运行,如果它是一个正确的算法,遗憾的是它不是.
任何人都能指出我正确的方向吗？
如果存在这样的元素,则多数表决算法决定序列中的哪个元素占多数.这是我在试图理解它时发现的最常被引用的链接.
http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
此外,我们在这里有一个讨论问题的链接:
问题是标记为正确的答案是错误的.请注意,该问题实际上允许输入具有单个元素的正好 N/2个副本(不一定多于 N/2,如通常在多数元素检测算法中假设的那样).
我复制了代码并尝试使用[1,2,3,2]和[1,2,3,2,6,2]等输入(产生3和6的结果).这实际上也适用于上面引用的算法(返回"无多数元素!").问题在于:只要多数元素和其他任何元素之间存在交替,就会选择数组中不是多数元素的最后一个元素.请更正我的错误想法,并告诉我如何在实施中避免它.
如果它发生的次数超过数组大小的一半,则此方法返回正整数数组中的数字,否则返回-1.我需要改进更大阵列的运行时间(10^5<size<10^8).有什么建议？
public static int findResult(int arr[],int len){
int val=0;
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<len;i++){
if(map.containsKey(arr[i])){
val = (Integer)map.get(arr[i]);
map.put(arr[i], val+1);
}else{
val=1;
map.put(arr[i], val);
}
}
Iterator<Integer> it=map.keySet().iterator();
while(it.hasNext()){
int next=it.next();
if((Integer)map.get(next)>(len/2)){
return next;
}
}
return -1;
}