一个整型数组中有一半以上的数是相同的,怎么找到这个数
日期：2014-05-20 浏览次数：20550 次
一个整型数组中有一半以上的数是相同的,如何找到这个数
一个整型数组中有一半以上的数是相同的,如何找到这个数? 用效率最高的方法, Arrays.sort(a,0,a.length);
------解决方案--------------------
我换个方式表述下你的问题：
“一个整型数组中，有一半以上的数是相同的，且其它数字都是绝对不相同的。”
是这样么？
那么似乎二分查找跟顺序查找的性能应该也没有什么差异，这个算法的主要问题是一开始都没有找的目标。
------解决方案--------------------
微软技术面试心得 寻找发帖水王
一节的基础题么
原书上标准解法是O(n)+常数内存
------解决方案--------------------
为性能考虑，可以做一个内部类，避免每次计数都要创建Integer对象，类似于：
一个整型数组中有一半以上的数是相同的,如何找到这个数? 用效率最高的方法, Arrays.sort(a,0,a.length);
------解决方案--------------------
我换个方式表述下你的问题：
“一个整型数组中，有一半以上的数是相同的，且其它数字都是绝对不相同的。”
是这样么？
那么似乎二分查找跟顺序查找的性能应该也没有什么差异，这个算法的主要问题是一开始都没有找的目标。
------解决方案--------------------
微软技术面试心得 寻找发帖水王
一节的基础题么
原书上标准解法是O(n)+常数内存
------解决方案--------------------
为性能考虑，可以做一个内部类，避免每次计数都要创建Integer对象，类似于：
- Java code
private static class Counter {
private int cnt;
public Counter inc() {
cnt++;
return this;
}
public int value() {
return cnt;
}
public String toString() {
return String.valueOf(cnt);
}
}
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
