Зводныя дыяпазоны Рашэнне Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў facebook Яндэкс
масіў

Пастаноўка праблемы

У зводных дыяпазонах праблема a сартаваны ўнікальны даецца цэлалікавы масіў. Мы павінны зрабіць найменшы адсартаваны спіс дыяпазонаў, якія пакрыць усе нумары ў масіў роўна адзін раз г.зн. кожны элемент масіва ахоплены роўна адным з дыяпазонаў.

Кожны дыяпазон [a, b] у спісе павінен выводзіцца як:

"A-> b", калі a! = B
"A", калі a == b

Прыклад

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, то яны не могуць належаць да аднаго дыяпазону.

Зводныя дыяпазоны Рашэнне Leetcode

Такім чынам, цяпер алгарытм просты. Мы павінны прайсціся па кожным суседнім элементам. Калі розніца паміж двума суседнімі лікамі большая за 1, мы павінны зрабіць новы дыяпазон для другога ліку. У адваротным выпадку, калі розніца роўна 1, мы паставім гэтую лічбу ў адзін і той жа дыяпазон.

Алгарытм

  1. Стварыце спіс радкоў для захоўвання выніку.
  2. Пачніце абход масіва з я = 0 да i<N, (N - памер масіва) у цыкле while.
    • Адзначце нумар у бягучым індэксе як Пачатак асартыменту.
    • Перабярыце масіў, пачынаючы з бягучага індэкса, і знайдзіце апошні элемент, адрозненне якога ад папярэдняга элемента роўна 1, г.зн. нумары [i + 1] == нумары [i] +1
    • Адзначыць гэты элемент як канец асартыменту.
    • Цяпер устаўце гэты сфармаваны дыяпазон у вынік спіс. І паўтарыце для астатніх элементаў.
  3. Вярнуць вынік спіс.

Рэалізацыя

Праграма C ++ для зводных дыяпазонаў

#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

Java-праграма для зводных дыяпазонаў

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): Дзе N - памер дадзенага масіва. Мы выкарыстоўваем дзве ўкладзеныя цыклы, але кожны элемент наведваем толькі адзін раз. Такім чынам, складанасць часу складае O (N).

Касмічная складанасць 

O (1): Мы не выкарыстоўваем ніякай дапаможнай прасторы, за выключэннем вяртання спіса радкоў.