解壓縮遊程長度編碼列表Leetcode解決方案


難度級別 容易獎學金
經常問 亞馬遜 蘋果 谷歌
排列

問題Decompress Run-Length Encoded List Leetcode Solution指出您得到了一個 排列 或包含序列的載體。 該序列具有一些特定的表示形式。 輸入序列由另一個序列形成。 我們將另一個序列稱為原始序列。 按照哪個順序創建輸入序列。 我們被要求找到原始序列。 序列中的每個奇數(ith)索引表示在原始序列中重複以下(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解決方案的方法

解壓縮運行長度編碼列表Leetcode解決方案是一個標準問題。 在各個公司進行的幾次編碼回合中,經常被問到。 該方法非常簡單,因為我們需要創建一個新數組來存儲原始序列。 我們只使用數組或向量,並繼續在後面添加元素。

我們可以運行一個for循環,該循環在每次迭代後跳2個單位。 這證實了我們僅處理(頻率,值)對。 現在再次使用嵌套的for循環,我們將第ith個索引處的元素添加到vector中。 我們按照給定輸入序列中第i + 1個索引處的元素運行嵌套的for循環。

解壓縮運行長度編碼列表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是輸出的長度。 由於我們存儲輸出是因為我們要返回它。 空間也被它佔據。