在一个规模为N的数组A中，所谓过半元素就是出现次数大于N/2的元素，例如
3.3.4.2.4.4.2.4.4
有一个过半元素4
给出一个算法，如果过半元素存在，，就找出来，否则给出报告
[b]问题补充：[/b]
我已经解决掉了这个问题了，对于一楼的那个算法我没有什么探讨，但是个人觉得有点不符合，二楼用了一个map把所有数组里的元素都放进去，一个个数，时间复杂度先不说，空间复杂度就够高的啦，下面是我的答案：
[code="java"]
class halfElement{
public static int find(int[] a){
int sum=1;
int x=a[0];
for(int i=1;i<a.length;i++){
if(a[i]==x){
sum=sum+1;
}else{
sum=sum-1;
}
if(sum<0){
x=a[i];
sum=1;
}
}
System.out.println(sum);
return x;
}
public static void main(String args[]){
int[] a={3, 3, 1, 2, 2, 2, 2, 4, 1};
int result=find(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+",");
}
System.out.println();
System.out.println(result);
}
}
[/code]
[b]问题补充：[/b]
昨天时间太匆忙了，没仔细看，我的算法的确有问题，非常感谢taopian 和etank的指点，但是我仍然比较想找出不借助任何数据结构，[b]原地[/b]找出过半元素的O(n)算法，对于两位提出的算法我其实一开始又考虑过，显然这是最基本的解决方法，但是如果能找到原地查找的算法何乐而不为呢？
首先我运行过lz的代码，答案是
[code="java"]
1
3,3,1,2,2,2,2,4,1,
2
[/code]
但是这个例子中有9个数，结果却找到了2，2只出现过4次，并没有超过半数，所以lz的这个算法有点问题
我的思路和taopian的一样，如果说时间复杂度是合格了的，关于空间复杂度最差情况下map的大小为n，但是如果可以提前得出没有过半数的结论就可以避免空间的浪费，所以我认为可以加一个限制，如果map的大小超过（n+1）/2，则表示没有过半的数；再就是考虑到遍历数组的问题，我觉得不必要完全遍历完数组才知道，次数最多的数如果也没有希望就肯定没有过半数了，所以对taopian的代码作了一点点改动
[code="java"]
public static void main(String[] args) throws Exception {
int[] nums = { 3, 3, 4, 2, 4, 4, 2, 4, 4 };
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int size = 0, max = 0;
for (int i = 0; i < num.length; i++) {
Integer sum = map.get(num[i]);
if (sum == null) {
map.put(num[i], 1);
if (++size > (num.length + 1)/2) {
System.out.println("No number match.");
}
} else {
++sum;
if (sum > num.length / 2) {
System.out.println(num[i]);
return;
} else {
map.put(num[i], sum);
if (max < sum) {
max = sum;
if ((max + (num.length - i -1)) <= num.length/2) {
System.out.println("No number match.");
}
}
}
}
}
for (Integer key : map.keySet()) {
System.out.println(key + " : " + map.get(key));
}
}
[/code]
java的解决方案：[code="java"]
List lst = new ArrayList();
lst.add(3);
... // 添加其他的内容
Collections.sort(lst);
Collections.binarySearch(lst, 你要查找的内容);
[/code]
c/c++解决方案：
[code="c"]
long BSearch(long lBegin, long lEnd, long* array, long value)
{
if(lBegin > lEnd)
return -1;
long tMidVal;
long lMidVal;
while(lBegin <= lEnd)
{
lMidVal = (lBegin + lEnd)>>1;
tMidVal = array[lMidVal];
if(tMidVal < value)
lBegin = lMidVal + 1;
else if(tMidVal > value)
lEnd = lMidVal - 1;
else
return lMidVal;
}
return -1;
}
[/code]
[code="java"]
public static void main(String[] args) throws Exception {
int[] nums = { 3, 3, 4, 2, 4, 4, 2, 4, 4 };
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
Integer sum = map.get(num);
if (sum == null) {
map.put(num, 1);
} else {
++sum;
if (sum > nums.length / 2) {
System.out.println(num);
return;
} else {
map.put(num, sum);
}
}
}
for (Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
}
[/code]
这样可以不？
楼主的代码明显有问题，我放个map，只是为了满足你最后找不到过半的元素，要打个统计出来而已。