요약 범위 Leetcode 솔루션


난이도 쉽게
자주 묻는 질문 페이스북 서비스 Yandex 주차
배열

문제 정책

요약 범위 문제 a 고유 한 정렬 정수 배열이 제공됩니다. 우리는 만들어야 가장 작은 정렬 범위 목록 모든 숫자를 포함 정렬 정확히 한 번 즉, 배열의 각 요소는 정확히 범위 중 하나에 포함됩니다.

목록의 각 범위 [a, b]는 다음과 같이 출력되어야합니다.

a! = b 인 경우 "a-> b"
a == b 인 경우 "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보다 크면 동일한 범위에 속할 수 없습니다.

요약 범위 Leetcode 솔루션

이제 알고리즘은 간단합니다. 인접한 각 요소에 대해 횡단해야합니다. 인접한 두 숫자의 차이가 1보다 크면 두 번째 숫자에 대해 새 범위를 만들어야합니다. 그렇지 않으면 차이가 정확히 1이면 그 숫자를 같은 범위에 넣습니다.

암호알고리즘

  1. 결과를 저장할 문자열 목록을 만듭니다.
  2. 어레이 순회 시작 i = 0 i<N, (N은 배열의 크기) while 루프에서.
    • 현재 색인의 숫자를 다음과 같이 표시하십시오. 스타트 범위의.
    • 현재 인덱스에서 시작하여 배열을 탐색하고 이전 요소와 정확히 1 차이가있는 마지막 요소를 찾습니다. nums [i + 1] == nums [i] +1
    • 이 요소를 다음으로 표시 종료 범위의.
    • 이제이 형성된 범위를 결과 명부. 나머지 요소에 대해 반복하십시오.
  3. 반환 결과 명부.

실시

요약 범위 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

요약 범위 Leetcode 솔루션을위한 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

요약 범위 Leetcode 솔루션에 대한 복잡성 분석

시간 복잡성

의 위에) : 여기서 N은 주어진 배열의 크기입니다. 두 개의 중첩 루프를 사용하고 있지만 모든 요소는 한 번만 방문합니다. 따라서 시간 복잡도는 O (N)입니다.

공간 복잡성 

O (1) : 문자열 목록을 반환하는 것 외에는 보조 공간을 사용하지 않습니다.