C++での最大ギャップ

ソートされていない配列があるとします。ソートされた形式で、連続する要素間の最大の違いを見つける必要があります。配列に含まれる要素が2つ未満の場合は、0を返します。したがって、配列が[12,3,9,1,17]の場合、並べ替えられた配列は[1,3,9,12,17]になるため、出力は6になり、5が最大差になります。 3と9の差は6です。

これを解決するには、次の手順に従います-

• minVal：=inf、maxCal：=-inf

• n：=numsのサイズ

• n <2の場合、0を返します;

• 0からn– 1 −

  の範囲のiの場合

  • minVal：=nums[i]とminValの最小値

  • maxVal：=nums[i]とmaxValの最大値

• ギャップ：=maxVal – minVal / n –1のセリング

• サイズn– 1のbucketMaxという1つの配列を作成し、これに–inf

  を入力します。

• サイズn– 1のbucketMinという1つの配列を作成し、これにinfを入力します

• 0からn– 1 −

  の範囲のiの場合

  • x：=nums [i]

  • x=minValまたはx=maxValの場合、次の部分をスキップして、次の反復に進みます

  • idx：=（nums [i] – minVal）/gap。

  • bucketMax [idx]：=bucketMax[idx]とnums[i]

    の最大値

  • bucketMin [idx]：=bucketMin[idx]とnums[i]

    の最小値

• ret：=0

• prev：=minVal

• 0からn–1の範囲のiの場合

  • bucketMax [i]=-infおよびbucketMin[i]=infの場合、次の部分をスキップして、次の反復に進みます

  • ret：=retとbucketMin[i]の最大値– prev

  • 前：=bucketMax [i]

• retの最大値を返す、maxVal-prev

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int maximumGap(vector<int>& nums) {
      lli minVal = INT_MAX;
      lli maxVal = INT_MIN;
      int n = nums.size();
      if(n < 2) return 0;
      for(int i = 0; i < n; i++){
         minVal = min((lli)nums[i], minVal);
         maxVal = max((lli)nums[i], maxVal);
      }
      int gap = ceil((double)(maxVal - minVal) / (double)(n - 1));
      vector <int> bucketMax(n - 1, INT_MIN);
      vector <int> bucketMin(n - 1, INT_MAX);
      for(int i = 0; i < n; i++){
         int x = nums[i];
         if(x == minVal || x == maxVal) continue;
         int idx = (nums[i] - minVal) / gap;
         bucketMax[idx] = max(bucketMax[idx], nums[i]);
         bucketMin[idx] = min(bucketMin[idx], nums[i]);
      }
      lli ret = 0;
      lli prev = minVal;
      for(int i = 0; i < n - 1; i++){
         if(bucketMax[i] == INT_MIN && bucketMin[i] == INT_MAX) continue;
         ret = max(ret, bucketMin[i] - prev);
         prev = bucketMax[i];
      }
      return max(ret, maxVal - prev);
   }
};
main(){
   Solution ob;
   vector<int> v = {12,3,9,1,17};
   cout << (ob.maximumGap(v));
}

入力

[12,3,9,1,17]

出力

6