Decompress Solution-и Рӯйхати рамзкардашудаи дарозмӯҳлати Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon себ Google
тартиботи ҳарбӣ

Масъалаи кушодани Рӯйхати рамзии даврии дарозмуддати Leetcode мегӯяд, ки ба шумо an асал ё вектори дорои пайдарпаӣ. Пасиҳамоӣ дорои якчанд намояндагии мушаххас мебошад. Пайдарпаии вуруд аз пайдарпайии дигар ташкил карда мешавад. Мо онро пайдарпаии дигарро ҳамчун пайдарпаии аслӣ меномем. Тибқи он, пайдарпайии вуруд сохта шудааст. Аз мо хоҳиш карда мешавад, ки пайдарпаии аслиро пайдо кунем. Ҳар як индекси тоқ (ith) дар пайдарпаӣ миқдори маротибаҳои такрори индекси зерин (i + 1th) -ро дар пайдарпаии аввал нишон медиҳад. Пас, чун ҳамеша, пеш аз ба ҳалли худ ғӯтав кардан, биёед якчанд мисолро дида бароем.

Decompress Solution-и Рӯйхати рамзкардашудаи дарозмӯҳлати 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

Масъалаи кушодани Рӯйхати Leetcode Рӯйхати рамзкардашудаи дарозмуддати рамзгузорӣ як роҳи стандартӣ аст. Ва дар якчанд давраҳои рамзгузорӣ, ки аз ҷониби ширкатҳои гуногун гузаронида мешаванд, зуд-зуд пурсида мешавад. Равиш хеле содда аст, зеро мо бояд барои нигоҳ доштани пайдарпаии аслӣ массиви нав созем. Мо танҳо массив ё векторро истифода мебарем ва дар қафо илова кардани элементҳоро идома медиҳем.

Мо метавонем for for -ро иҷро кунем, ки пас аз ҳар як такрор 2 адад ҷаҳида гузарад. Ин тасдиқ мекунад, ки мо танҳо бо ҷуфтҳои (басомад, арзиш) сарукор дорем. Ҳоло боз бо ҳалқаи nested for, мо унсури индекси ith -ро ба вектор илова мекунем. Мо барои давр nested барои як унсурро дар индекси 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 дарозии натиҷа аст. Азбаски мо натиҷаҳоро нигоҳ медорем, зеро мо онро бармегардонем. Фазоро низ он ишғол мекунад.