सारांश दायरा Leetcode समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ फेसबुक Yandex
एरे

समस्या वक्तव्य

सारांश दायरा समस्यामा a क्रमबद्ध अद्वितीय पूर्णांक एरे दिइयो। हामीले बनाउनु पर्छ सब भन्दा सानो क्रमबद्ध दायरा सूची मा सबै नम्बर कभर गर्नुहोस् array ठीक एक पटक अर्थात् एर्रेको प्रत्येक तत्व दायरा मध्ये कुनै एक द्वारा कभर गरिएको छ।

प्रत्येक दायरा [a, b] सूचीमा आउटपुट हुनु पर्छ:

"A-> b" यदि a! = B
"A" यदि a == b

उदाहरणका

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

व्याख्या:

दायराहरू हुन्:
"०-> २" ले संख्याहरू कभर गर्दछ {०, १, २}
"->” "ले नम्बरहरू कभर गर्दछ {,,}}
"” "ले अंक covers {कभर गर्दछ

तसर्थ यसले एरेको सबै नम्बरहरू एक पटक कभर गर्दछ।

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

व्याख्या:

दायराहरू हुन्:
[०,०] -> "०"
[२,2,4] -> "२->” "
[०,०] -> "०"
[२,8,9] -> "२->” "

दृष्टिकोण

माथि उल्लेख गरिए अनुसार हामीले दायराको साना सूची बनाउनु पर्छ। तसर्थ यदि दुई आसन्न तत्त्वहरू १ फरक फरक गर्दछ भने यो समान दायरामा सम्बन्धित हुनुपर्दछ। अर्कोतर्फ यदि दुई आसन्न तत्त्वहरू १ भन्दा ठूलो हुन्छ भने, तिनीहरू समान दायरामा पर्न सक्दैनन्।

सारांश दायरा Leetcode समाधान

त्यसैले अब एल्गोरिथ्म सरल छ। हामीले प्रत्येक आसन्न तत्त्वहरूको लागि ट्रान्सभर्स गर्नु पर्छ। यदि दुई आसन्न संख्या बीचको भिन्नता १ भन्दा ठूलो छ भने हामीले दोस्रो नम्बरको लागि नयाँ दायरा बनाउनु पर्छ। अन्यथा यदि फरक ठीक १ छ भने हामी त्यो संख्यालाई समान दायरामा राख्नेछौं।

अल्गोरिदम

  1. परिणाम भण्डारण गर्न स्ट्रि stringको सूची सिर्जना गर्नुहोस्।
  2. बाट एरे ट्र्याभर्सिंग शुरू गर्नुहोस् i = ० गर्न i<N, (N एर्रेको साइज हो) केही समयको लूपमा।
    • हालको अनुक्रमणिकामा नम्बर मार्क गर्नुहोस् यस रूपमा सुरु दायरा को।
    • हालको अनुक्रमणिकाबाट सुरू हुने एर्रे ट्रान्सवर्स गर्नुहोस् र अन्तिम तत्व फेला पार्नुहोस् जसको अघिल्लो तत्त्वको भिन्नता ठीक १ हो, अर्थात् संख्याहरू [i + 1] == संख्याहरू [i] +१
    • यस तत्वलाई मार्क गर्नुहोस् अन्त दायरा को।
    • अब यस बनेको दायरा लाई मा राख्नुहोस् परिणाम सूची र बाँकी तत्वहरूको लागि दोहोर्याउनुहोस्।
  3. फिर्ता परिणाम सूची।

कार्यान्वयन

C ++ सारांश दायरा Leetcode समाधानको लागि कार्यक्रम

#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

सारांश दायरा लीटकोड समाधानको लागि जटिलता विश्लेषण

समय जटिलता

O (N): जहाँ एन दिइएको एरेको आकार हो। यद्यपि हामी दुई नेस्टेड लूपहरू प्रयोग गर्दैछौं तर प्रत्येक तत्व एक पटक मात्र भेटिन्छ। त्यसैले समय जटिलता ओ (एन) हो।

ठाउँ जटिलता 

O (१): स्ट्रिंगहरूको सूची फिर्ता बाहेक हामी कुनै सहयोगी स्थान प्रयोग गरिरहेका छैनौं।