[Leetcode]-Reverse Integer

[Leetcode]-Reverse Integer

題目：Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.
找出數組中出現超過? n/2 ?次的數據
三種解法：
1、參考別人的，很巧的解法
2、插入排序，排序後，nums? n/2 ?必定是出現超過? n/2 ?次的數據，而且插入排序在數據接近排序好的順序的時候，時間復雜度為O（n）
3、快排，和2一樣，只不過速度稍快 12ms

You may assume that the array is non-empty and the majority element always exist in the array.

typedef int elementtype;
//infact CUT = 10 is the best solution
#define CUT 10  
void swap(int *a,int *b)  
{  
    int tem = *a;  
    *a  = *b;  
    *b  = tem;  
}  
void insertion(elementtype A[],int n)  
{  
    int p = 0 ;  
    int j = 0 ;  
    for(p=1;p0&&A[j-1]>tem;j--)  
        {  
             A[j] = A[j-1];  
        }  
        A[j] = tem;  
    }  

}  
elementtype median3(elementtype A[],int left ,int right)  
{  
    int center = (left +right) / 2;  
    if(A[left]>A[center])  
        swap(&A[left],&A[center]);  
    if(A[left]>A[right])  
        swap(&A[left],&A[right]);  
    if(A[center]>A[right])  
        swap(&A[center],&A[right]);  

    swap(&A[center],&A[right-1]);  

    return A[right-1];  
}  
void Qsort(elementtype A[],int left, int right)  
{  
    int i,j;  
    elementtype pivot;  

    if(left + CUT<= right)  
    {  
        pivot = median3(A,left,right); //select middle element as pivot  
        i = left;j = right-1;  
        for(;;)  
        {  
            while(A[++i]pivot){}  
            if(i0&&nums[j-1]>tem;j--)  
        {  
             nums[j] = nums[j-1];  
        }  
        nums[j] = tem;  
    }  
    return nums[numsSize/2];
    */

    //solution 3 qiuk sort :12ms
    Qsort(nums,0,numsSize-1);  
    return nums[numsSize/2];

}