Ұзындықтағы кодталған тізімнің декомпрессивті шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Amazon алма Google
Array

Шешімнің декомпрессиялық шешімі, Leetcode Solution шешімінің шешімі сізге берілгенін айтады массив немесе тізбекті қамтитын вектор. Тізбектің белгілі бір көрінісі бар. Кіріс тізбегі басқа тізбектен қалыптасады. Біз мұны бастапқы рет ретінде тағы бір реттік деп атаймыз. Осыған сәйкес кіріс тізбегі құрылды. Бізден түпнұсқа тізбекті табу сұралады. Әрбір тақ (ith) индексі келесі (i + 1-ші) индекс бастапқы ретпен бірнеше рет қайталану санын білдіреді. Сонымен, шешімге сүңгу алдында әрқашан бірнеше мысалға тоқталайық.

Ұзындықтағы кодталған тізімнің декомпрессивті шешімі

nums = [1,2,3,4]
[2,4,4,4]

Түсіндіру: Шығарылымның дұрыстығын тексерейік? 2 бастапқы тұжырымда 1 рет қайталанады. Сонымен, енгізу дәйектілігінде ол 1, 2 болуы керек. Осыдан кейін 4 3 рет қайталанады, бұл кіріс дәйектілігінде де көрінеді, демек, бұл шығудың дұрыс екендігін дәлелдейді.

nums = [1,1,2,3]
[1,3,3]

Түсініктеме: егер біз нәтижені тексеретін болсақ. 1-нің жалғыз данасы бар, ал 3-і екі рет қайталанады. Шығарылым тағы да дұрыс.

Ұзындықтағы кодталған тізімді декомпресстеу әдісі, Leetcode шешімі

Шешімнің декомпрессорлық шешімі, Leetcode Solution стандартты шешімі. Әр түрлі компаниялар өткізетін бірнеше кодтау кезеңінде жиі сұралады. Бұл тәсіл өте қарапайым, өйткені біз бастапқы тізбекті сақтау үшін жаңа массив құруымыз керек. Біз жай ғана массивті немесе векторды қолданамыз және артында элементтерді қосуды жалғастырамыз.

Біз әр қайталанғаннан кейін 2 бірлікке секіретін for циклін іске қосамыз. Бұл біздің (жиілік, мән) жұптармен ғана айналысатынымызды растайды. Енді қайтадан кірістірілген циклмен ith индексіндегі элементті векторға қосамыз. Біз берілген кіру ретіндегі i + 1 индексіндегі элемент бойынша кірістірілген циклды орындаймыз.

Шифрланған тізімнің декомпресстік коды, Leetcode шешімінің тізімі

C ++ коды

#include <bits/stdc++.h>
using namespace std;

vector<int> decompressRLElist(vector<int>& nums) {
    vector<int> tmp;
    for(int i=0;i<nums.size();i+=2){
        for(int j=0;j<nums[i];j++)
            tmp.push_back(nums[i+1]);
    }
    return tmp;
}

int main(){
    vector<int> input = {1,2,3,4};
    vector<int> output = decompressRLElist(input);
    for(auto x: output)cout<<x<<" ";
}
2 4 4 4

Java коды

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int[] decompressRLElist(int[] nums) {
        int size = 0, k = 0;
        for(int i=0;i<nums.length;i+=2)
            size += nums[i];
        int[] tmp = new int[size];
        for(int i=0;i<nums.length;i+=2){
            for(int j=0;j<nums[i];j++)
                tmp[k++] = nums[i+1];
        }
        return tmp;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] input = {1,2,3,4};
      int[] output = decompressRLElist(input);
      for(Integer x: output)System.out.print(x+" ");
  }
}
2 4 4 4

Күрделілікті талдау

Уақыттың күрделілігі

O (N), мұндағы N - шығыс ұзындығы. Мұнда уақыттың күрделілігі кіріске байланысты емес. Кірістің орнына уақыттың күрделілігі алынған нәтижеге немесе алынған нәтижеге байланысты.

Ғарыштың күрделілігі

O (N), мұндағы N - шығыс ұзындығы. Біз өнімді қайтарып жатқандықтан сақтаймыз. Кеңістікті де ол алып жатыр.