面试题29：数组中出现次数超过一半的数字

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

分析：

如果一个数字才数组中出现的次数超过了数组长度的一半，那么对这个数组进行排序，位于数组中间位置的那个数就是出现次数超过一半的那个数。对数组排序的时间复杂度是O(nlog(n))，但是对于这道题目，还有更好的算法，能够在时间复杂度O(n)内求出。我们写过快速排序算法，其中的Partition()方法是一个最重要的方法，该方法返回一个index，能够保证index位置的数是已排序完成的，在index左边的数都比index所在的数小，在index右边的数都比index所在的数大。那么本题就可以利用这样的思路来解。

1. 通过Partition()返回index，如果index==mid，那么就表明找到了数组的中位数；如果index<mid，表明中位数在[index+1,end]之间；如果index>mid，表明中位数在[start,index-1]之间。知道最后求得index==mid循环结束。
2. 根据求得的index，遍历一遍数组，每当出现一个等于index所指向的数时time++，最后判断time是否大于数组长度的一半，如果大于则表明index所指向的数就是所求的数，如果不是，则表明不存在一个数出现的次数超过数组长度的一半。

代码实例：

#include<iostream>
#include<stdlib.h>
using namespace std;

//函数声明
int MoreThanHalf(int arry[],int start,int end,int len);//函数入口
int Partition(int arry[],int start,int end);//返回一个index，使index左边的数都比index所在的数小，index右边的数都比index所在数大
bool CheckMoreThanHalf(int arry[],int len,int result);//判断一个数在数组中是否有超过一半

int Partition(int arry[],int start,int end)
{
    int pivotkey=arry[start];
    while(start<end)
    {
        while(start<end&&arry[end]>=pivotkey)
            end--;
        arry[start]=arry[end];
        while(start<end&&arry[start]<=pivotkey)
            start++;
        arry[end]=arry[start];
    }
    arry[start]=pivotkey;
    return start;
}

bool CheckMoreThanHalf(int arry[],int len,int result)
{
    int time=0;
    for(int i=0;i<len;i++)
    {
        if(arry[i]==result)
            ++time;
    }

    bool isMoreThanHalf=true;
    if(time*2<=len)
        isMoreThanHalf=false;
    return isMoreThanHalf;
}

int MoreThanHalf(int arry[],int start,int end,int len)
{
    if(arry==NULL&&len<=0)
        return -1;

    int index=Partition(arry,start,end);
    int middle=len/2;//中间位置
    while(index!=middle)
    {
        if(index>middle)//如果调整数组以后获得的index大于middle，则继续调整start到index-1区段的数组
            index=Partition(arry,start,index-1);
        else//否则调整index+1到end区段的数组
            index=Partition(arry,index+1,end);
    }
    //最后获取的index=middle，此时在middle左边的数小于arry[middle]，在其右边的数大于arry[middle]
    int result=arry[middle];
    if(!CheckMoreThanHalf(arry,len,result))
        return -1;

    return arry[middle];
}

void main()
{
    //int arry[]={5,1,7,3,0,2,8};//定义数组
    int arry[]={2,2,1,1,3};//定义数组
    int len=sizeof(arry)/sizeof(int);//求数组长度

    int half=MoreThanHalf(arry,0,len-1,len);
    cout<<half<<endl;

    system("pause");
}

题目变种

一个文件中有每一个保存一个单词，其中有一个单词出现的次数超过一半，求这个次数超过一半的单词。

解体思路

这道题目其实本质上跟前面的求出现次数超过一半的数是一样的，只不过是这里要求的是单词出现次数，而前面是整数出现次数。如果是整数的话，可以通过一个整型数组来完成求中位数的操作。但是这里是字符串了，我们想再用求中位数的方法，只能通过LinkedList这个集合累来完成。

首先我们遍历一次问价，将所有单词都保存到LinkedList当中去，然后求排在中间的那个单词。LinkedList中的元素使有序的，不像ArrayList中的元素那样是无序的。而且List中允许元素重复。

代码实现

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Iterator;
import java.util.LinkedList;

public class GetMoreThanHalfWords {

    public static void main(String args[]) {
        GetMoreThanHalfWords gmthw = new GetMoreThanHalfWords();
        
        LinkedList<String> list =new LinkedList<String>();
        gmthw.buildLinkedList(list);
        //两种输出LinkedList的方法
        //gmthw.printLinkedList(list);
        //gmthw.printLinkedList2(list);
        System.out.println(gmthw.getMoreThanHalf(list));
        
        /**
         * 测试String的compareTo方法
        String a="apple";
        String b="orange";
        System.out.println(a.compareTo(b));
        System.out.println(b.compareTo(a));
        */
        
    }

    // 第一步：创建LinkedList,将文件中的单词保存到LinkedList当中。
    public void buildLinkedList(LinkedList<String> list) {
        try {
            FileReader reader = new FileReader("words2.txt");
            BufferedReader br = new BufferedReader(reader);

            String s = null;
            while ((s = br.readLine()) != null) {
                list.add(s);
            }
            br.close();
            reader.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public String getMoreThanHalf(LinkedList<String> list)
    {
        int len=list.size();
        int mid=len/2;
        int start=0;
        int end=len-1;
        int index=partition(list,len,start,end);
        while(index!=mid)//index总会等于mid的
        {
            if(index>mid)
            {
                end=index-1;
                index=partition(list,len,start,end);
            }
            else
            {
                start=index+1;
                index=partition(list,len,start,end);
            }
        }
        //到这里index=mid
        return list.get(index);
    }
    
    public int partition(LinkedList<String> list,int len,int start,int end)
    {
        String s=list.get(start);
        while(start<end)
        {
            //找出第一个
            while(start<end&&s.compareTo(list.get(end))<=0)
                end--;
            list.set(start, list.get(end));
            while(start<end&&s.compareTo(list.get(start))>=0)
                start++;
            list.set(end, list.get(start));
        }
        list.set(start, s);
        return start;
    }
    
    // 打印LinkedList中的值
    //方法1
    public void printLinkedList(LinkedList<String> list) {
        Iterator it = list.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
    //方法2
    public void printLinkedList2(LinkedList<String> list) {
        for(int i=0;i<list.size();i++)
        {
            System.out.println(list.get(i));
        }
    }
}