747_至少是其他数字两倍的最大数

风扫地

1. 在一个给定的数组nums中，总是存在一个最大元素 。
   
2. 
   
3. 查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
   
4. 
   
5. 如果是，则返回最大元素的索引，否则返回-1。
   
6. 
   
7. 示例 1:
   
8. 
   
9. 输入: nums = [3, 6, 1, 0]
   
10. 输出: 1
    
11. 解释: 6是最大的整数, 对于数组中的其他整数,
    
12. 6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.
    
13. 
    
14. 
    
15. 
    
16. 示例 2:
    
17. 
    
18. 输入: nums = [1, 2, 3, 4]
    
19. 输出: -1
    
20. 解释: 4没有超过3的两倍大, 所以我们返回 -1.
    
21. 提示:
    
22.     nums 的长度范围在[1, 50].
    
23.     每个 nums[i] 的整数范围在 [0, 99].
    
24. 来源：力扣（LeetCode）
    
25. 
    

复制代码

风扫地

1. /*方法1:常规方法,两次循环找最大第二大数对应的index,然后比较.*/
   
2. int dominantIndex(int* nums, int numsSize)
   
3. {
   
4.     int ret_index       =   -1  ;
   
5.     int firstMaxIndex   =   0   ;
   
6.     int secondMaxIndex  =   0   ;
   
7.     int i               =   0   ;
   
8.    
   
9.     do
   
10.     {   
    
11.         if(numsSize == 1)
    
12.         {
    
13.             ret_index = 0;
    
14.             break;
    
15.         }
    
16.         for(i = 0; i < numsSize ; i++)
    
17.         {
    
18.             if(nums[i]>nums[firstMaxIndex])
    
19.             {
    
20.                 firstMaxIndex = i;
    
21.             }
    
22.         }
    
23.         
    
24.         if(firstMaxIndex==0)
    
25.         {
    
26.             secondMaxIndex = 1;
    
27.         }
    
28.         
    
29.         for(i=0;i<numsSize;i++)
    
30.         {
    
31.             if(i==firstMaxIndex)
    
32.             {
    
33.                 continue;
    
34.             }
    
35.             
    
36.             if(nums[i]>nums[secondMaxIndex])
    
37.             {
    
38.                 secondMaxIndex = i;
    
39.             }
    
40.         }
    
41.         if(nums[firstMaxIndex] >=2*nums[secondMaxIndex])
    
42.         {
    
43.             ret_index = firstMaxIndex;
    
44.         }
    
45.     }while(0);
    
46. 
    
47. 
    
48.     return ret_index;
    
49. }
    
50. 
    
51. /*
    
52. 执行结果：通过
    
53. 显示详情
    
54. 执行用时 :4 ms, 在所有 C 提交中击败了92.81%的用户
    
55. 内存消耗 :6.9 MB, 在所有 C 提交中击败了79.49%的用户
    
56. */

复制代码

风扫地

方法2: 将原始数据heapify为大顶堆,取堆顶和孩子节点中较大的值,然后找出最值和第二大的值做做比較,若比較成功,在通過最值去查詢索引
显然,也可以使用索引堆降低查询索引的时间,此处未实现。

1. void __shift_down(int* data, int size, int ind)
   
2. {
   
3.     int moreBiggerIndex =   0;
   
4.     int temp            =   0;
   
5.     while(2*ind<=size) /* 有左孩子就是有孩子*/
   
6.     {
   
7.         moreBiggerIndex = 2*ind;
   
8.         if(  (moreBiggerIndex+1<=size)
   
9.            &&(data[moreBiggerIndex+1]>data[moreBiggerIndex])
   
10.         )
    
11.         {
    
12.             moreBiggerIndex += 1; /* 更新到右孩子*/   
    
13.         }
    
14.         
    
15.         if(data[ind]<data[moreBiggerIndex])
    
16.         {
    
17.             temp = data[ind];
    
18.             data[ind] = data[moreBiggerIndex];
    
19.             data[moreBiggerIndex] = temp;
    
20.             ind = moreBiggerIndex;
    
21.         }
    
22.         else
    
23.         {
    
24.             break;
    
25.         }
    
26. 
    
27.     }
    
28. }
    
29. 
    
30. void maxHeapify(int* nums , int size)
    
31. {
    
32.     int i = 0;
    
33.     for(i=size/2;i>=1;i--)
    
34.     {
    
35.         __shift_down(nums,size,i);
    
36.     }
    
37.    
    
38. }
    
39. 
    
40. /*方法2:将原始数据heapify为大顶堆,取堆顶和孩子节点中较大的值,然后找出最值和第二大的值做做比較,若比較成功,在通過最值去查詢索引
    
41. 显然,也可以使用索引堆降低查询索引的时间,此处未实现。
    
42. 
    
43. */
    
44. int dominantIndex(int* nums, int numsSize)
    
45. {
    
46.     int     ret_val         = -1;
    
47.     int*    nums_buf        = NULL;
    
48.     int     i               = 0;
    
49.     int     secondMaxInd    = 0;
    
50.     int     finded          = 0;
    
51.     do
    
52.     {
    
53.         if(numsSize == 1)
    
54.         {
    
55.             ret_val = 0;
    
56.             break;
    
57.         }
    
58.         
    
59.         nums_buf = (int*)malloc(sizeof(int)*(numsSize+1));
    
60.         if(nums_buf==NULL)
    
61.         {
    
62.             break;
    
63.         }
    
64.         nums_buf[0] = 0;
    
65.         for(i=1;i<=numsSize;i++)
    
66.         {
    
67.             nums_buf[i] = nums[i-1];
    
68.         }
    
69.         
    
70.         maxHeapify(nums_buf,numsSize);
    
71.         secondMaxInd = 2;
    
72.         if(   ((secondMaxInd+1)<=numsSize)
    
73.             &&(nums_buf[secondMaxInd+1]>nums_buf[secondMaxInd])
    
74.         )
    
75.         {
    
76.             secondMaxInd++;
    
77.         }
    
78.         
    
79.         if(nums_buf[1] >= 2*nums_buf[secondMaxInd])
    
80.         {
    
81.             ret_val = nums_buf[1];
    
82.             finded = 1;
    
83.         }
    
84. 
    
85.         
    
86.     }while(0);
    
87.    
    
88.    
    
89.    
    
90.     if(nums_buf!=NULL)
    
91.     {
    
92.         free(nums_buf);
    
93.         nums_buf = NULL;
    
94.     }
    
95.    
    
96.     if(finded!=0)
    
97.     {
    
98.         for(i=0;i<numsSize;i++)
    
99.         {
    
100.             if(nums[i]==ret_val)
     
101.             {
     
102.                 ret_val = i;
     
103.                 break;
     
104.             }
     
105.         }
     
106.     }
     
107.     return ret_val;
     
108. }
     
109. 
     
110. 
     
111. /*
     
112. 执行结果：通过
     
113. 显示详情
     
114. 执行用时 :4 ms, 在所有 C 提交中击败了92.65% 的用户
     
115. 内存消耗 :6.9 MB, 在所有 C 提交中击败了80.77%的用户
     
116. */

复制代码