229. 多数元素 II-快速排序加计数统计法

229. 多数元素 II-快速排序加计数统计法

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

输入：nums = [3,2,3]
输出：[3]

示例 2：

输入：nums = [1]
输出：[1]

示例 3：

输入：nums = [1,2]
输出：[1,2]

今天做的后两个题目感觉挺像的，后面两个属于一种计数题目类型，感兴趣的，可以学习一下，此题解题代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

 
int cmp(const void* a, const void* b)
 {
     return *(int*)a - *(int*)b;
 }


void quick_sort(int *a,int low,int high){
    int l=low,h=high;
    if(low<high){
        int p=a[low];
        while(low<high){
            while(low<high&&a[high]>=p){
                high--;

            }
            a[low]=a[high];
            while(low<high&&a[low]<=p){
                low++;
            }
            a[high]=a[low];
        }
        a[low]=p;
        quick_sort(a,l,low-1);
        quick_sort(a,low+1,h);

    }
}

int* majorityElement(int* nums, int numsSize, int* returnSize){
    int threshold=numsSize/3;
    
    qsort(nums,numsSize,sizeof(int),cmp);
    //quick_sort(nums,0,numsSize-1);
    int pre=nums[0]+1;
    int count=1;
    int size=0;
   
    for(int i=0;i<numsSize;i++){
        if(nums[i]==pre){
            count++;
        }
        else{
            count=1;
            pre=nums[i];
        }
        if(count>threshold){
            while(nums[i]==pre){
                i++;
                if(i==numsSize){
                    break;
                }
            }
            i--;
        
            nums[size++]=pre;
        }
    }
     *returnSize=size;
        return nums;


}