414. Third Maximum Number

- 日理万妓 2022-06-08 00:51 109阅读 0赞

/*
    
    Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
    
    Example 1:
    
    Input: [3, 2, 1]
    
    Output: 1
    
    Explanation: The third maximum is 1.
    
    Example 2:
    
    Input: [1, 2]
    
    Output: 2
    
    Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
    
    Example 3:
    
    Input: [2, 2, 3, 1]
    
    Output: 1
    
    Explanation: Note that the third maximum here means the third maximum distinct number.
    Both numbers with value 2 are both considered as second maximum.
    
    */
    //66ms 3.41%
    //思路：先把数组排一遍序，用快速排序，然后去重复元素，这些都是我之前写好的leetcode题目中写好的函数，直接拿过来用了。然后输出第三个大数
    int thirdMax(int* nums, int numsSize) {
        int length;
        quicksort(nums,0,numsSize-1);
        length = removeDuplicates(nums,numsSize);
        if(length<3)
            return nums[length-1];
        return nums[length-3];
    }
    void quicksort(int* nums,int left,int right)
    {
        int i,j,t,temp;
        if(left>right)
           return;
    
        temp=nums[left]; //temp中存的就是基准数
        i=left;
        j=right;
        while(i!=j)
        {
                       //顺序很重要，要先从右边开始找
                       while(nums[j]>=temp && i<j)
                                j--;
                       //再找右边的
                       while(nums[i]<=temp && i<j)
                                i++;
                       //交换两个数在数组中的位置
                       if(i<j)
                       {
                                t = nums[i];
                                nums[i] = nums[j];
                                nums[j] = t;
                       }
        }
        //最终将基准数归位
        nums[left] = nums[i];
        nums[i] = temp;
    
        quicksort(nums,left,i-1);//继续处理左边的，这里是一个递归的过程
        quicksort(nums,i+1,right);//继续处理右边的 ，这里是一个递归的过程
    }
    int removeDuplicates(int* nums, int numsSize) {
        int i,count = 1;
        if(nums[0]==NULL&&numsSize==0)
            return NULL;
        for(i=0;i<numsSize-1;i++)
            if(nums[i]!=nums[i+1])
                nums[count++] = nums[i+1];
        return count;
    }