4/12-剑指offer

1.数组中出现次数超过一半的数字
思路一：数组中出现次数超过一半的数字是排好序后数组的中位数，我们采用随机快速排序的思路，先在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中数字小的数字都在他的左面，大的都在他的右面。如果选中数字的下标刚好是2/n，这个数就是中位数，如果小于，则中位数位于其右面，如果大于，中位数位于其左面。可以继续进行递归查找。
注：要注意无效操作的情况（数组为空，长度小于1），以及数组中本来就没有出现次数超过一半的数字。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int len=numbers.size();
        if(len<=0) return 0;
        int mid=len>>1;
        int start=0;
        int end=len-1;
        int index=Partition(numbers,len,start,end);
        while(index!=mid)
        {
            if(index>mid)
            {
                end=index-1;
                index=Partition(numbers,len,start,end);//中位数在左面
            }
            else
            {
                start=index+1;
                index=Partition(numbers,len,start,end);//中位数在右面
            }
        }
        int result=numbers[index];
        int times=0;
        for(int i=0;i<len;i++)
        {
            if(numbers[i]==result)
                times++;//判断出现次数是否超过一半
        }
        return times*2>len?result:0;  
    }
    int Partition(vector<int> &numbers,int length,int start,int end)//快排核心函数
    {
        if(length<=0||start<0||end>=length)
            return false;
        int index=RandomInRange(start,end);
        Swap(&numbers[index],&numbers[end]);//随机生成一个点，与尾结点互换
        int small=start-1;
        for(index=start;index<end;index++)
        {
            if(numbers[index]<numbers[end])
            {
                ++small;
                if(small!=index)
                    Swap(&numbers[index],&numbers[small]);//说明small与index直接有大于end下标的数字
            }
        }
        ++small;
        Swap(&numbers[small],&numbers[end]);
        return small;
    }
    int RandomInRange(int start,int end)
   {
         srand (time(NULL));
         return rand() % (end-start+1) + start;//随机数函数
   }
    void Swap(int *a,int *b)
    {
        int temp=*a;
        *a=*b;
        *b=temp;
    }
};

思路二：遍历数组时保存两个值，一个是数组中的一个数字，一个是次数，如果下一个数字与此数字相同，那么次数加一，如果不相同，次数减一。如果次数为0，那么保存下一个数字，重置次数为1.由于要找的数字出现的次数比其他所有数字出现的次数之和还要多，因此最后一个次数被设为1的数字就是要找的数字。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int len=numbers.size();
        if(len<=0) return 0;
        int result=numbers[0];//当前数
        int count=1;//次数
        for(int i=1;i<len;i++)
        {
            if(numbers[i]!=result)
            {
                count--;//不等于，次数--
            }
            else
            {
                count++;//等于，次数++
            }
            if(count==0)
            {
                result=numbers[i];
                count=1;//次数为0，重置
            }
        }
        int times=0;
        for(int i=0;i<len;i++)
        {
            if(numbers[i]==result)
                times++;
        }
        return times*2>len?result:0;  //加一个判断
    }
};

2.最小的k个数
思路一：仍基于快排，如果基于数组的第k个数字来调整，则使得比第k个数字小的所有数字都位于数组的左边，比k个数字大的所有数字都位于数组的右边，这样调整之后，位于数组左中左边的k个数字就是最小的k个数字。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        int len=input.size();
        if(len<=0||k<=0||k>len) return res;
        int start=0;
        int end=len-1;
        int index=Partition(input,len,start,end);
        while(index!=k-1)
        {
            if(index>k-1)
            {
                end=index-1;
                index=Partition(input,len,start,end);
            }
            else
            {
                start=index+1;
                index=Partition(input,len,start,end);
            }
        }//直到index为k时，此时前k个数就是最小的k个数
        for(int i=0;i<k;i++)
            res.push_back(input[i]);
        return res;
    }
    int Partition(vector<int> &numbers,int length,int start,int end)//快排核心函数
    {
        if(length<=0||start<0||end>=length)
            return false;
        int index=RandomInRange(start,end);
        Swap(&numbers[index],&numbers[end]);//随机生成一个点，与尾结点互换
        int small=start-1;
        for(index=start;index<end;index++)
        {
            if(numbers[index]<numbers[end])
            {
                ++small;
                if(small!=index)
                    Swap(&numbers[index],&numbers[small]);//说明small与index直接有大于end下标的数字
            }
        }
        ++small;
        Swap(&numbers[small],&numbers[end]);
        return small;
    }
    int RandomInRange(int start,int end)
   {
         srand (time(NULL));
         return rand() % (end-start+1) + start;//随机数函数
   }
    void Swap(int *a,int *b)
    {
        int temp=*a;
        *a=*b;
        *b=temp;
    }
};

思路二：用于处理海量数据，利用最大堆（根节点的值总是大于它的子树中任意节点的值）或者红黑树（STL里面的set和multiset）

class Solution {
public:
    typedef multiset<int,greater<int>> intSet;
    typedef multiset<int,greater<int>>::iterator setIterator;
    void GetLeastNumbers_Solution(const vector<int> &input, int k,intSet& leastNumbers) {        
        leastNumbers.clear();
        if(k<1||input.size()<k) return;
        vector<int>::const_iterator iter=input.begin();
        for(;iter!=input.end();iter++)
        {
            if(leastNumbers.size()<k)
            {
                leastNumbers.insert(*iter);//先插入k个数
            }
            else
            {
                setIterator iterGreatest=leastNumbers.begin();
                if(*iter<*(leastNumbers.begin()))
                {
                    leastNumbers.erase(iterGreatest);
                    leastNumbers.insert(*iter);//如果小于set里的最大值，就替换掉最大值
                }
            }
        }
    }
};

3.数据流中的中位数
思路一：如题1，利用快速排序的partition函数寻找中位数。
思路二：最大堆和最小堆。

class Solution {
public:
    vector<int> res;
    void Insert(int num)
    {
        res.push_back(num);
    }

    double GetMedian()
    { 
        sort(res.begin(),res.end());
        int len=res.size();
        if(len%2==1)
            return (double)res[len/2];
        else
            return (double)((res[len/2]+res[len/2-1])/2.0);

    }

};