Декомпресирайте решение за кодиран списък с дължина на изпълнение с Leetcode


Ниво на трудност Лесно
Често задавани в Амазонка ябълка Google
Array

Проблемът Декомпресиране на кодиран списък с дължина на изпълнение Leetcode Solution гласи, че сте получили масив или вектор, съдържащ последователност. Последователността има някакво специфично представяне. Входната последователност се формира от друга последователност. Ще наречем тази друга последователност като оригинална последователност. Според която е създадена входната последователност. От нас се иска да намерим оригиналната последователност. Всеки нечетен (i-ти) индекс в последователността представлява броя на повторенията на следващия (i + 1-ти) индекс в оригиналната последователност. Така че, както винаги преди да се потопите в решението, нека разгледаме няколко примера.

Декомпресирайте решение за кодиран списък с дължина на изпълнение с Leetcode

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 Solution

Проблемът Декомпресиране на кодирания списък с дължина на изпълнение с Leetcode Solution е стандартен. И се задава често в няколко кръга за кодиране, провеждани от различни компании. Подходът е много прост, тъй като трябва да създадем нов масив за съхраняване на оригиналната последователност. Ние просто използваме масив или вектор и продължаваме да добавяме елементи отзад.

Можем да изпълним цикъл for, който скача 2 единици след всяка итерация. Това потвърждава, че имаме работа само с двойки (честота, стойност). Сега отново с вложен цикъл for, добавяме елемента с i-тия индекс към вектор. Изпълняваме вложения цикъл for според елемента при 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

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

Сложност във времето

НА), където N е дължината на изхода. Тук времевата сложност не зависи от входа. Вместо вход, сложността на времето зависи от резултата или получения резултат.

Сложност на пространството

НА), където N е дължината на изхода. Тъй като съхраняваме изхода, защото го връщаме. Пространството също е заето от него.