સારાંશ શ્રેણીઓ લેટકોડ સોલ્યુશન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ફેસબુક યાન્ડેક્ષ
અરે

સમસ્યા નિવેદન

સારાંશ રેન્જમાં સમસ્યા એ અનન્ય સortedર્ટ પૂર્ણાંક એરે આપવામાં આવે છે. આપણે બનાવવું પડશે સૌથી નાના સortedર્ટ કે રેન્જ યાદી માં બધા નંબરો આવરી લે છે એરે બરાબર એકવાર એટલે કે એરેનો દરેક તત્વ રેન્જમાં એક બરાબર આવરી લેવામાં આવે છે.

સૂચિમાંની દરેક શ્રેણી [a, b] નું આઉટપુટ આ હોવું જોઈએ:

"A-> બી" જો એ! = બી
“A” જો a == બી

ઉદાહરણ

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

સમજૂતી:

શ્રેણીઓ છે:
"0-> 2" માં સંખ્યાઓ આવરી લેવામાં આવે છે {0, 1, 2}
"4-> 5" નંબરોને આવરી લે છે {4, 5}
"7" નંબરોને આવરે છે {7}

તેથી તે એરેની બધી સંખ્યાને બરાબર એકવાર આવરી લે છે.

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

સમજૂતી:

શ્રેણીઓ છે:
[0,0] -> "0"
[2,4] -> "2-> 4"
[6,6] -> "6"
[8,9] -> "8-> 9"

અભિગમ

ઉપર જણાવ્યા મુજબ આપણે રેન્જની સૌથી નાની સૂચિ બનાવવી પડશે. તેથી જો બે અડીને તત્વો 1 તફાવતથી ભિન્ન હોય તો તે સમાન શ્રેણીથી સંબંધિત હોવો જોઈએ. બીજી બાજુ જો બે અડીને તત્વોનો તફાવત 1 કરતા વધારે હોય, તો પછી તે સમાન શ્રેણીના હોઈ શકતા નથી.

સારાંશ શ્રેણીઓ લેટકોડ સોલ્યુશન

તેથી હવે અલ્ગોરિધમનો સરળ છે. આપણે દરેક સંલગ્ન તત્વો માટે પસાર કરવું પડશે. જો બે અડીને નંબરો વચ્ચેનો તફાવત 1 કરતા વધારે છે, તો પછી આપણે બીજા નંબર માટે નવી શ્રેણી બનાવવી પડશે. અન્યથા જો તફાવત બરાબર 1 છે, તો અમે તે સંખ્યાને સમાન શ્રેણીમાં મૂકીશું.

અલ્ગોરિધમ

  1. પરિણામ સંગ્રહવા માટે શબ્દમાળાઓની સૂચિ બનાવો.
  2. થી એરે ટ્રversવર્સ કરવાનું પ્રારંભ કરો હું = 0 સુધી i<એન, (એન એરેનું કદ છે) જ્યારે લૂપમાં.
    • વર્તમાન અનુક્રમણિકા પર આના પર ચિહ્નિત કરો શરૂઆત શ્રેણીની.
    • વર્તમાન અનુક્રમણિકાથી શરૂ થતા એરેને પસાર કરો અને છેલ્લું તત્વ શોધો જેનો પાછલા તત્વથી તફાવત બરાબર 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

સારાંશ રેન્જ્સ લેટકોડ સોલ્યુશન માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન): જ્યાં એન આપેલ એરેનું કદ છે. તેમ છતાં અમે બે નેસ્ટેડ લૂપ્સનો ઉપયોગ કરી રહ્યાં છીએ પરંતુ દરેક તત્વની મુલાકાત માત્ર એક જ વાર કરવામાં આવે છે. તેથી સમય જટિલતા ઓ (એન) છે.

અવકાશ જટિલતા 

ઓ (1): અમે શબ્દમાળાઓની સૂચિ પરત કરવા સિવાય કોઈ સહાયક જગ્યા વાપરી રહ્યા નથી.