题目：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;p<n;p++ ) { elementtype tem = A[p] ; for(j=p;j>0&&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){} while(A[--j]>pivot){} if(i<j) swap(&A[i],&A[j]); else break; } swap(&A[i],&A[right-1]); Qsort(A,left,i-1); Qsort(A,i+1,right); } else insertion(A+left,right-left+1); } int majorityElement(int* nums, int numsSize) { //solution 1 :13ms /* int cnt = 0, res; for (int i = 0; i < numsSize; ++i) { if (cnt == 0) res = nums[i]; if (res == nums[i]) ++cnt; else --cnt; } return res; */ //solution 2 insertion sort :28ms /* int p = 0 ; int j = 0 ; for(p=1;p<numsSize;p++ ) { int tem = nums[p] ; for(j=p;j>0&&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]; }转载于:https://www.cnblogs.com/bhlsheji/p/5118782.html
相关资源：数据结构—成绩单生成器