-
Notifications
You must be signed in to change notification settings - Fork 1
/
414. Third Maximum Number
81 lines (65 loc) · 2.17 KB
/
414. Third Maximum Number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*
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;
}