Декомпресирајте го решението за шифриран кодиран список со должина на траење


Ниво на тешкотија Лесно
Често прашувано во Амазон Јаболко Google
Низа

Проблемот Декомпресирај го списокот со шифрирана шифра со должина на трчање изјавува дека ви е даден низа или вектор кој содржи низа. Низата има одредена специфична претстава. Влезната низа е формирана од друга низа. Ние ќе ја наречеме таа друга низа како оригинална низа. Според која е создадена влезната низа. Од нас се бара да ја пронајдеме оригиналната низа. Секој непарен (и) индекс во низата претставува број на пати што се повторува следниот (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 се повторува двапати. Уште еднаш излезот е точен.

Пристап за декомпресирање на решението за шифриран код со шифрирана должина на трчање

Проблемот Декомпресирај го списокот со шифрирана шифрирана шифра со долг рок е стандарден. И често се прашува во неколку рунди за кодирање спроведени од разни компании. Пристапот е многу едноставен бидејќи треба да создадеме нова низа за да ја зачуваме оригиналната низа. Ние едноставно користиме низа или вектор и продолжуваме да додаваме елементи во задниот дел.

Можеме да извршиме јамка за која скока 2 единици по секоја повторување. Ова потврдува дека се занимаваме само со парови (фреквенција, вредност). Сега повторно со вметната јамка, го додаваме елементот на ith индексот на векторот. Ние работиме вметната за јамка според елементот на i + 1-ви индекс во дадената низа на влез.

Код за декомпресија Решение за код за шифрирање шифрирано со должина на траење

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

Анализа на сложеност

Временска комплексност

НА), каде што N е должината на излезот. Тука, временската сложеност не зависи од влезот. Наместо влез, временската сложеност зависи од резултатот или добиениот резултат.

Комплексноста на просторот

НА), каде што N е должината на излезот. Бидејќи го чуваме излезот затоа што го враќаме. Просторот е окупиран и од него.