0


数组中的最大间距(巨难)

1.对应letecode链接:

  1. 最大间距 - 力扣(LeetCode)

2.题目描述:

3.解题思路:

1.我们很容易就能够想到时间复杂度为O(N*logN)的算法,然后再遍历一遍数组求相邻两个数的最大差值即可。但这与题目要求的时间复杂度O(N)不符。

下面我们来看一下这种不是人能够想得到的解法:

2.利用计数排序的思想,先求出原数组的最大值

max

与最小值

min

.

利用桶排序的思想,根据原数组的长度 n,创建出 n 个桶,每一个桶代表一个区间范围。其中第 0个桶从原数组的最小值 min 开始,区间跨度为(max - min) / (n - 1)。下面我们以无序数组

{ 2, 6, 3, 4, 5, 10, 9 }为例:

3.遍历所有的桶,统计出每一个桶的最大值,和这个桶右侧非空桶的最小值的差,数值最大的差即为原数组排序后的相邻最大差值

第 2 步,遍历原数组,确定每个桶内的最大和最小值。

3.遍历原数组,把原数组每一个元素插入到对应的桶中,记录每一个桶的最大和最小值。

4.对应代码:

class Solution {
public:
    int maximumGap(vector<int>& nums) {
          if(nums.size()<2){
              return 0;
          }
          int len=nums.size();
          int MaxVal=INT_MIN;
          int MinVal=INT_MAX;
          for(auto ch:nums)
          {
              MaxVal=max(MaxVal,ch);
              MinVal=min(MinVal,ch);
          }
          if(MinVal==MaxVal){//说明只有一种数
              return 0;
          }
          //不止一种数一定有range,len个数len+1一个桶
          vector<bool>hasNum(len+1);
          //保存第i号桶的最大值和最小值
          vector<int>maxs(len+1);
          vector<int>mins(len+1);
          int bid=0;
          for(int i=0;i<nums.size();i++){
            bid=bucket(nums[i],len,MinVal,MaxVal);//获取每个数应该去那个桶
            mins[bid]=hasNum[bid]?min(mins[bid],nums[i]):nums[i];//更新桶里面的最小值和最大值
            maxs[bid]=hasNum[bid]?max(maxs[bid],nums[i]):nums[i];
            hasNum[bid]=true;
          }
          int res=0;
          int lastMax=maxs[0];
          //答案不可能来自同一个桶内
          int i=1;
          for(;i<=len;i++){
              if(hasNum[i]){//计算差值
                  res=max(res,mins[i]-lastMax);
                  lastMax=maxs[i];
              }
          }
          return res;
    }

    int bucket(long num,long len,long Min,long Max){//确定桶号
        return (int)((num-Min)*len/(Max-Min));
    }

};

注意:代码实现这里N个数对应N+1个桶原理类似。


本文转载自: https://blog.csdn.net/qq_56999918/article/details/125352076
版权归原作者 一个山里的少年 所有, 如有侵权,请联系我们删除。

“数组中的最大间距(巨难)”的评论:

还没有评论