风扫地 发表于 2019-7-9 14:42:58

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

在一个给定的数组nums中，总是存在一个最大元素 。

查找数组中的最大元素是否至少是数组中每个其他数字的两倍。

如果是，则返回最大元素的索引，否则返回-1。

示例 1:

输入: nums =
输出: 1
解释: 6是最大的整数, 对于数组中的其他整数,
6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.



示例 2:

输入: nums =
输出: -1
解释: 4没有超过3的两倍大, 所以我们返回 -1.
提示:
    nums 的长度范围在.
    每个 nums 的整数范围在 .
来源：力扣（LeetCode）

风扫地 发表于 2019-7-9 14:46:39

/*方法1:常规方法,两次循环找最大第二大数对应的index,然后比较.*/
int dominantIndex(int* nums, int numsSize)
{
    int ret_index       =   -1;
    int firstMaxIndex   =   0   ;
    int secondMaxIndex=   0   ;
    int i               =   0   ;
   
    do
    {   
      if(numsSize == 1)
      {
            ret_index = 0;
            break;
      }
      for(i = 0; i < numsSize ; i++)
      {
            if(nums>nums)
            {
                firstMaxIndex = i;
            }
      }
      
      if(firstMaxIndex==0)
      {
            secondMaxIndex = 1;
      }
      
      for(i=0;i<numsSize;i++)
      {
            if(i==firstMaxIndex)
            {
                continue;
            }
            
            if(nums>nums)
            {
                secondMaxIndex = i;
            }
      }
      if(nums >=2*nums)
      {
            ret_index = firstMaxIndex;
      }
    }while(0);


    return ret_index;
}

/*
执行结果：通过
显示详情
执行用时 :4 ms, 在所有 C 提交中击败了92.81%的用户
内存消耗 :6.9 MB, 在所有 C 提交中击败了79.49%的用户
*/

风扫地 发表于 2019-7-9 14:49:10

本帖最后由 风扫地 于 2019-7-10 22:01 编辑

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

void __shift_down(int* data, int size, int ind)
{
    int moreBiggerIndex =   0;
    int temp            =   0;
    while(2*ind<=size) /* 有左孩子就是有孩子*/
    {
      moreBiggerIndex = 2*ind;
      if((moreBiggerIndex+1<=size)
         &&(data>data)
      )
      {
            moreBiggerIndex += 1; /* 更新到右孩子*/   
      }
      
      if(data<data)
      {
            temp = data;
            data = data;
            data = temp;
            ind = moreBiggerIndex;
      }
      else
      {
            break;
      }

    }
}

void maxHeapify(int* nums , int size)
{
    int i = 0;
    for(i=size/2;i>=1;i--)
    {
      __shift_down(nums,size,i);
    }
   
}

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

*/
int dominantIndex(int* nums, int numsSize)
{
    int   ret_val         = -1;
    int*    nums_buf      = NULL;
    int   i               = 0;
    int   secondMaxInd    = 0;
    int   finded          = 0;
    do
    {
      if(numsSize == 1)
      {
            ret_val = 0;
            break;
      }
      
      nums_buf = (int*)malloc(sizeof(int)*(numsSize+1));
      if(nums_buf==NULL)
      {
            break;
      }
      nums_buf = 0;
      for(i=1;i<=numsSize;i++)
      {
            nums_buf = nums;
      }
      
      maxHeapify(nums_buf,numsSize);
      secondMaxInd = 2;
      if(   ((secondMaxInd+1)<=numsSize)
            &&(nums_buf>nums_buf)
      )
      {
            secondMaxInd++;
      }
      
      if(nums_buf >= 2*nums_buf)
      {
            ret_val = nums_buf;
            finded = 1;
      }

      
    }while(0);
   
   
   
    if(nums_buf!=NULL)
    {
      free(nums_buf);
      nums_buf = NULL;
    }
   
    if(finded!=0)
    {
      for(i=0;i<numsSize;i++)
      {
            if(nums==ret_val)
            {
                ret_val = i;
                break;
            }
      }
    }
    return ret_val;
}


/*
执行结果：通过
显示详情
执行用时 :4 ms, 在所有 C 提交中击败了92.65% 的用户
内存消耗 :6.9 MB, 在所有 C 提交中击败了80.77%的用户
*/
页: [1]
查看完整版本: 747_至少是其他数字两倍的最大数