خلاصہ حدود لیٹکوڈ حل


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے فیس بک Yandex
لڑی

مسئلہ یہ بیان

سمری رینجز میں a الگ الگ الگ عددی سرنی دی گئی ہے۔ ہمیں بنانا ہے سب سے چھوٹی ترتیب کہ حدود کی فہرست میں تمام نمبروں کا احاطہ کریں صف بالکل ایک بار یعنی سرنی کا ہر عنصر حدود میں سے ایک کے ذریعہ احاطہ کرتا ہے۔

فہرست میں ہر رینج [a، b] کی پیداوار اس طرح ہونی چاہئے:

"a-> b" اگر a! = b
"a" اگر a == b

مثال کے طور پر

nums = [0,1,2,4,5,7]
["0->2","4->5","7"]

وضاحت:

حدود یہ ہیں:
"0-> 2" میں نمبر covers 0، 1، 2 covers شامل ہیں
"4-> 5" میں نمبر covers 4، 5 covers شامل ہیں
"7" نمبروں پر محیط ہے covers 7}

لہذا اس میں صفوں کی ایک بڑی تعداد بالکل ایک بار شامل ہے۔

nums = [0,2,3,4,6,8,9]
["0","2->4","6","8->9"]

وضاحت:

حدود یہ ہیں:
[0,0،0] -> "XNUMX"
[2,4،2] -> "4-> XNUMX"
[6,6،6] -> "XNUMX"
[8,9،8] -> "9-> XNUMX"

نقطہ نظر

جیسا کہ اوپر بتایا گیا ہے کہ ہمیں حدود کی سب سے چھوٹی فہرست بنانی ہوگی۔ لہذا اگر دو ملحقہ عناصر 1 فرق سے مختلف ہیں تو پھر اس کا تعلق ایک ہی حد سے ہونا چاہئے۔ دوسری طرف اگر دو ملحقہ عناصر کا فرق 1 سے زیادہ ہے تو وہ ایک ہی حد سے تعلق نہیں رکھ سکتے ہیں۔

خلاصہ حدود لیٹکوڈ حل

تو اب الگورتھم آسان ہے. ہمیں ہر ایک سے ملحق عناصر سے گزرنا ہے۔ اگر دو ملحقہ نمبروں کے درمیان فرق 1 سے زیادہ ہو تو ہمیں دوسرے نمبر کے ل for ایک نئی حد بنانی ہوگی۔ بصورت دیگر اگر فرق بالکل 1 ہے تو ہم اس تعداد کو ایک ہی حد میں ڈالیں گے۔

الگورتھم

  1. نتائج کو ذخیرہ کرنے کے لئے تار کی ایک فہرست بنائیں۔
  2. سے سرنی کو عبور کرنا شروع کریں میں = 0 کے لئے i<N ، (N صف کا سائز ہے) تھوڑی دیر میں لوپ میں۔
    • موجودہ انڈیکس پر نمبر کو بطور نشان زد کریں شروع کریں رینج کی.
    • موجودہ انڈیکس سے شروع ہونے والی صف کو عبور کریں اور آخری عنصر تلاش کریں جس کے پچھلے عنصر سے فرق بالکل 1 ہے ، یعنی نمبر [i + 1] == نمبر [i] +1
    • اس عنصر کو بطور نشان زد کریں آخر رینج کی.
    • اب اس میں قائم رینج کو داخل کریں نتیجہ فہرست اور باقی عناصر کے لئے دہرائیں۔
  3. واپس نتیجہ فہرست.

عمل

سی ++ پروگرام برائے سمری رینجز لیٹکوڈ حل

#include <bits/stdc++.h>
using namespace std;

vector<string> summaryRanges(vector<int>& nums) 
{
    vector<string> res;
    int i=0,n=nums.size();
    while(i<n)
    {
        int start,end;

        start=nums[i];            
        while(i+1<n && nums[i+1]==nums[i]+1) i++;
        end=nums[i];

        if(start==end)
            res.push_back(to_string(start));
        else
            res.push_back(to_string(start) + "->" + to_string(end));

        i++;
    }

    return res;
}

int main() 
{   
    vector<int> nums={0,1,2,4,5,7};
    vector<string> res= summaryRanges(nums);
    
    for(auto str:res) cout<< str <<endl;
    
    return 0; 
}
0->2
4->5
7

جاوا پروگرام برائے سمری رینجز لیٹکوڈ حل

import java.util.*;
class Rextester{
    
    public static List<String> summaryRanges(int[] nums) 
    {      
        List<String> res= new ArrayList<String>();
        
        int i=0,n=nums.length;
        while(i<n)
        {
            int start,end;
            
            start=nums[i];            
            while(i+1<n && nums[i+1]==nums[i]+1) i++;
            end=nums[i];
            
            if(start==end)
                res.add(start + "");
            else
                res.add( start + "->" + end );
            
            i++;          
        }
        
        return res;
    }
    
  public static void main(String args[])
    {
        int[] nums={0,1,2,4,5,7};
        List<String> res= summaryRanges(nums);
        
        for(String str:res)
            System.out.println(str);
    }
}
0->2
4->5
7

سمری حدود لیٹکوڈ حل کے ل Comp پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N): جہاں N دیئے گئے صفوں کا سائز ہے۔ اگرچہ ہم دو گھونسلے والے لوپ استعمال کر رہے ہیں لیکن ہر عنصر کا صرف ایک بار دورہ کیا جاتا ہے۔ لہذا وقت کی پیچیدگی O (N) ہے۔

خلائی پیچیدگی 

O (1): ہم کوئی معاون جگہ استعمال نہیں کر رہے ہیں سوائے تاروں کی فہرست واپس کرنے کے۔