Кыскача чечүү аралыгы


Кыйынчылык деңгээли жеңил
Көп суралган Facebook Яндекс
согуштук тизме

Маселени билдирүү

Жыйынтык диапазондо көйгөй а уникалдуу иреттелген бүтүн массив берилген. Биз жасашыбыз керек кичинекей иреттелген диапазондорунун тизмеси бардык сандарды камтыйт согуштук тизме так бир жолу башкача айтканда, массивдин ар бир элементин диапазондун бири камтыйт.

Тизмедеги ар бир [a, b] диапазону төмөнкүдөй чыгарылышы керек:

“A-> b” болсо, а! = B
A == b болсо, "a"

мисал

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

Explanation:

Аралыгы:
"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"]

Explanation:

Аралыгы:
[0,0] -> “0”
[2,4] -> “2-> 4”
[6,6] -> “6”
[8,9] -> “8-> 9”

жакындоо

Жогоруда айтылгандай, биз диапазондордун эң кичинекей тизмесин түзүшүбүз керек. Демек, эгер жанаша турган эки элемент 1 айырма менен айырмаланса, анда ал бир эле диапазонго кириши керек. Башка жагынан алганда, эгер жанаша турган эки элементтин айырмасы 1ден жогору болсо, анда алар бир диапазонго кире албайт.

Кыскача чечүү аралыгы

Ошентип, азыр алгоритм жөнөкөй. Ар бир чектеш элементтер үчүн өтүшүбүз керек. Эгерде жанаша турган эки сандын ортосундагы айырмачылык 1ден чоң болсо, анда экинчи санга жаңы диапазон чыгарышыбыз керек. Болбосо, эгер айырмачылык так 1 болсо, анда биз ал санды бирдей аралыкка коёбуз.

Algorithm

  1. Натыйжаны сактоо үчүн сап тизмесин түзүңүз.
  2. Массивди аралап баштаңыз i = 0 чейин i<N, (N - массивдин көлөмү) while циклинде.
    • Учурдагы индекстеги номурду төмөнкүдөй белгилеңиз баштоо диапазондун
    • Массивди учурдагы индекстен баштап кыдырып, мурунку элементтен айырмасы так 1 болгон акыркы элементти табыңыз, б.а. nums [i + 1] == nums [i] +1
    • Бул элементти белгилөө Бир мезгилдин акырына карата диапазондун
    • Эми бул түзүлгөн диапазонду жыйынтык тизме. Жана калган элементтер үчүн кайталаңыз.
  3. Return the жыйынтык тизме.

ишке ашыруу

Кыскача диапазондогу Leetcode чечими үчүн 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 программасы Leetcode Solution

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

Кыскача диапазондогу комплекстик анализ Leetcode Solution

Убакыт татаалдыгы

O (N): Бул жерде N - берилген массивдин көлөмү. Эки уяны колдонуп жатабыз, бирок ар бир элементке бир эле жолу барышат. Демек, убакыттын татаалдыгы O (N).

Космостун татаалдыгы 

O (1): Биз саптардын тизмесин кайтаруудан башка эч кандай кошумча мейкиндикти колдонбой жатабыз.