一道笔试题,时间复杂度要求O(N)
int数组中有三个元素出现的次数超过元素总个数的1/4,在规定时间复杂度下,求出这三个数。
我的思路,交卷的一刹那,我发现自己考虑非常不全面。
定义三个变量,保存三个数,在定义三个计数器,开始把a[0],a[1],a[2]赋给三个变量(这里有问题,万一重复了),然后对后面的数组扫描,出现相等的计数器加一,不相等计数器减一。
已经通知下午2点面试,晚上再跟大家探讨下,这题其实跟数组中有元素超过数组一半是一类问题吧,可能考虑起来要复杂点。
请用C/C++实现,Java我不熟。
//多谢@ zonxin @brayden 这是编程之美 寻找发帖水王扩展问题,代码如下,参考网址
void find3(int * ID, int n)
{
int candidate[3];
int nTimes[3] = {0};
int i;
for (i = 0; i < n; i++)
{
if(nTimes[0] == 0)
{
if(ID[i] == candidate[1])
nTimes[1]++;
else if (ID[i] == candidate[2])
nTimes[2]++;
else
{
candidate[0] = ID[i];
nTimes[0]++;
}
}
else if (nTimes[1] == 0)
{
if(ID[i] == candidate[0])
nTimes[0]++;
else if (ID[i] == candidate[2])
nTimes[2]++;
else
{
candidate[1] = ID[i];
nTimes[1]++;
}
}
else if (nTimes[2] == 0)
{
if(ID[i] == candidate[0])
nTimes[0]++;
else if (ID[i] == candidate[1])
nTimes[1]++;
else
{
candidate[2] = ID[i];
nTimes[2]++;
}
}
else
{
if(ID[i] == candidate[0])
nTimes[0]++;
else if(ID[i] == candidate[1])
nTimes[1]++;
else if(ID[i] == candidate[2])
nTimes[2]++;
else
nTimes[0]--, nTimes[1]--, nTimes[2]--;
}
}
printf("三个水王ID分别是:%d,%d,%d\n", candidate[0], candidate[1], candidate[2]);
}
用Java写了一个,应该不是很准确。
使用c语言的话原理是一样的,也是使用哈希表来实现,只是C语言不好定义哈希的大小。
我的代码
import java.util.*;
/**
* Created by Nicholas on 2015/10/11.
*/
public class Soluction {
/**
* @brief 使用hashmap,时间复杂度是O(N),空间复杂度是O(n)
* @param data 目标数组
* @return list结果
*/
public static List<Integer> getNumbers(int[] data){
List<Integer> result = new ArrayList<>();
if(data==null || data.length<=4)
return result;
Map<Integer,Integer> map = new HashMap<>();
/**
* 使用hashmap,其中的key是数组中元素的值,value是出现的次数
* 当检测到已经出现key时,将key的value加一
*/
for(int i = 0;i<data.length;i++){
if(map.containsKey(data[i]))
map.put(data[i],map.get(data[i])+1);
else
map.put(data[i],1);
}
int critical = data.length/4;
/**
* 遍历这个hashmap,找出value大于1/4 总大小的 key
*/
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
if(entry.getValue()>critical)
result.add(entry.getKey());
}
return result;
}
public static void main(String[] args) {
int[] data = {1,1,1,1,2,2,2,2,3,3,3,3,4,5,6};
List<Integer> result = Soluction.getNumbers(data);
for (Iterator<Integer> iter = result.iterator();iter.hasNext();){
System.out.println(iter.next());
}
}
}