414_第三大的数

风扫地

1. /*
   
2. 给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
   
3. 示例 1
   
4. 输入 [3, 2, 1]
   
5. 输出 1
   
6. 解释 第三大的数是 1.
   
7. 示例 2
   
8. 输入 [1, 2]
   
9. 输出 2
   
10. 解释 第三大的数不存在, 所以返回最大的数 2 .
    
11. 示例 3
    
12. 输入 [2, 2, 3, 1]
    
13. 输出 1
    
14. 解释 注意，要求返回第三大的数，是指第三大且唯一出现的数。
    
15. 存在两个值为2的数，它们都排第二。
    
16. */

复制代码

解法：堆排序后再取

1. int     count = 0;
   
2. int*    arr   = NULL;
   
3. 
   
4. 
   
5. void _swap(int* a, int*b)
   
6. {
   
7.     int c;
   
8.     c = *a;
   
9.     *a = *b;
   
10.     *b = c;
    
11. }
    
12. 
    
13. 
    
14. void shift_up( int ind )
    
15. {
    
16.     while(  (arr[ind/2] < arr[ind])   /*大根堆:父节点的值小于新加入的孩子节点,且 ind/2 至少为1 均满足时才交换*/
    
17.           &&(ind > 1)
    
18.          )
    
19.     {
    
20.         _swap(&arr[ind/2],&arr[ind]);   /* 交换 */
    
21.          ind /= 2;                      /* 待比较对象迁移到父节点*/
    
22.     };
    
23. }
    
24. 
    
25. void shift_down( int ind )
    
26. {
    
27.     int moreBiggerIndex = 0;
    
28.     while(2*ind <=count) /* 有左孩子就是有孩子*/
    
29.     {
    
30.         moreBiggerIndex = 2*ind;
    
31.         if(  (moreBiggerIndex+1<=count)
    
32.            &&(arr[moreBiggerIndex+1]>arr[moreBiggerIndex])
    
33.         )
    
34.         {
    
35.             moreBiggerIndex += 1; /* 更新到右孩子*/   
    
36.         }
    
37.         if(arr[ind]<arr[moreBiggerIndex])
    
38.         {
    
39.             _swap(&arr[ind],&arr[moreBiggerIndex]);
    
40.             ind = moreBiggerIndex;
    
41.         }
    
42.         else
    
43.         {
    
44.             break;
    
45.         }
    
46.     };
    
47. }
    
48. 
    
49. 
    
50. int search_ele(int num)
    
51. {
    
52.     int ret_val = 0;
    
53.    
    
54.     for(int i = 1; i <= count ; i++)
    
55.     {
    
56.         if(arr[i] == num)
    
57.         {
    
58.             ret_val = 1;
    
59.             break;
    
60.         }
    
61.     }   
    
62.     return ret_val ;
    
63. }
    
64. 
    
65. void insert_ele(int num)
    
66. {
    
67.     if(search_ele(num) == 1)
    
68.     {
    
69.         return;
    
70.     }
    
71.     else
    
72.     {
    
73.         arr[count+1] = num;
    
74.         count ++;
    
75.         shift_up(count);        
    
76.     }
    
77. }
    
78. 
    
79. int getMax(int* ret_val)
    
80. {
    
81.     int item;
    
82.     if(count < 1)
    
83.     {
    
84.         //cout << "此二叉堆已经为空,无法进行取出操作" << endl;
    
85.         return -1;
    
86.     }
    
87.    
    
88.     /* 获得根节点 */
    
89.     item = arr[1];
    
90.     _swap(&arr[1],&arr[count]); /*把最后一个和第一个进行交换*/
    
91.     count--;                    /* 进行计数调整*/
    
92.     shift_down(1);              /*把交换上来的数进行shift_down操作,以使堆继续满足大根堆的性质*/
    
93. 
    
94.     *ret_val = item;
    
95.     return 0;
    
96. }
    
97. 
    
98. int thirdMax(int* nums, int numsSize)
    
99. {
    
100.     int ret_val = 0;
     
101.     arr = (int*)malloc(sizeof(int)*(numsSize+1));
     
102.     if(arr == NULL)
     
103.     {
     
104.         return 0;
     
105.     }
     
106.     else
     
107.     {
     
108.         memset(arr,0,sizeof(int)*(numsSize+1));
     
109.     }
     
110.    
     
111.     for(int i = 0 ; i < numsSize ; i++)
     
112.     {
     
113.         insert_ele(nums[i]);
     
114.     }
     
115. 
     
116.     if (count < 3)
     
117.     {
     
118.         getMax(&ret_val);
     
119.     }
     
120.     else
     
121.     {
     
122.         for (int i = 0; i < 3; i++)
     
123.         {
     
124.             if (getMax(&ret_val) == -1)
     
125.             {
     
126.                 break;
     
127.             }
     
128.         }
     
129.     }
     
130.     free(arr);
     
131.     arr = NULL;
     
132.     count = 0;
     
133.     return ret_val;
     
134. }
     

复制代码

1. /*
   
2. 资源和用时都爆炸了。。
   
3. 执行用时 : 148 ms, 在Third Maximum Number的C提交中击败了9.00% 的用户
   
4. 内存消耗 : 7.6 MB, 在Third Maximum Number的C提交中击败了6.67% 的用户
   
5. */

复制代码

风扫地

解法2：
利用4个元素的小顶堆进行优先队列处理，降低复杂度到O(nlog4)即O(n) ，编写中。。。