首页 > 其他 > 详细

Chap5: question: 29 - 31

时间:2014-05-02 10:45:08      阅读:390      评论:0      收藏:0      [点我收藏+]

29. 数组中出现次数超过一半的数字.

方法a. 排序取中       O(nlogn).

方法b. partition 函数分割找中位数          >=O(n).

方法c. 设计数变量,扫描一遍。     O(n).

#include <stdio.h>
bool Invalid_Input = false;
int getNumber(int data[], int length){
    Invalid_Input = false;
    if(!data || length < 1) { Invalid_Input = true; return 0; }
    int count = 1, value = data[0];
    for(int i = 1; i < length; ++i)
    {
        if(count == 0){
            value = data[i];
            count = 0;
        }else if(data[i] == value){
            ++count;
        }else
            --count;
    }
    return value;
}
int main(){
    int numbers[] = {2, 2, 2, 2, 6, 6, 6, 6, 6};
    int value = getNumber(numbers, sizeof(numbers) / 4);
    if(value && !Invalid_Input)
        printf("%d\n", value);
    return 0;
}
bubuko.com,布布扣

Chap5: question: 29 - 31,布布扣,bubuko.com

Chap5: question: 29 - 31

原文:http://www.cnblogs.com/liyangguang1988/p/3703688.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!