सी ++ में विभिन्न सूचियों से चुने गए तत्वों के बीच सबसे छोटा अंतर खोजने का कार्यक्रम

मान लीजिए कि हमारे पास सूचियों की एक सूची है, हमें प्रत्येक सूची से एक मान चुनकर और चुने गए तत्व की अधिकतम और न्यूनतम संख्या के बीच के अंतर को लेकर सबसे छोटा अंतर खोजना होगा।

इसलिए, यदि इनपुट सूचियों की तरह है =[[30, 50, 90], [85], [35, 70]], तो आउटपुट 20 होगा, क्योंकि हम 90, 85, 70 और 90 - 70 =ले सकते हैं। 20

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मैक्सवैल :=-इन्फ

• रिट :=inf

• प्राथमिकता कतार pq परिभाषित करें

• n :=सूचियों का आकार

• इनिशियलाइज़ i :=0 के लिए, जब i

  • सरणी सूचियों को क्रमबद्ध करें [i]

  • pq में {सूचियाँ [i, 0], i, 0} डालें

  • maxVal :=अधिकतम सूचियाँ[i, 0] और maxVal

• जबकि pq का आकार n के समान है, −

  . करें

  • एक सरणी अस्थायी परिभाषित करें =pq के ऊपर

  • pq से शीर्ष तत्व हटाएं

  • ret :=न्यूनतम रिट और (maxVal - temp[0])

  • तापमान के अंतिम तत्व को बढ़ाएं

  • यदि अस्थायी का अंतिम तत्व <सूचियों का आकार [अस्थायी [1]], तो

    • maxVal :=maxVal की अधिकतम और सूचियाँ[temp[1], temp का अंतिम तत्व]

    • अस्थायी [0]:=सूचियाँ [अस्थायी [1], अस्थायी का अंतिम तत्व]

    • pq में अस्थायी डालें

• वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
struct Cmp {
   bool operator()(vector<int>& a, vector<int>& b) {
      return !(a[0] < b[0]);
   }
};
class Solution {
   public:
   int solve(vector<vector<int>>& lists) {
      int maxVal = INT_MIN;
      int ret = INT_MAX;
      priority_queue<vector<int>, vector<vector<int>>, Cmp> pq;
      int n = lists.size();
      for (int i = 0; i < n; i++) {
         sort(lists[i].begin(), lists[i].end());
         pq.push({lists[i][0], i, 0});
         maxVal = max(lists[i][0], maxVal);
      }
      while (pq.size() == n) {
         vector<int> temp = pq.top();
         pq.pop();
         ret = min(ret, maxVal - temp[0]);
         temp.back()++;
         if (temp.back() < lists[temp[1]].size()) {
            maxVal = max(maxVal, lists[temp[1]][temp.back()]);
            temp[0] = lists[temp[1]][temp.back()];
            pq.push(temp);
         }
      }
      return ret;
   }
};
int solve(vector<vector<int>>& lists) {
   return (new Solution())->solve(lists);
}
int main(){
   vector<vector<int>> v = {{30, 50, 90},{85},{35, 70}};
   cout << solve(v);
}

इनपुट

{{30, 50, 90},{85},{35, 70}}

आउटपुट

20