ரன்-நீள குறியாக்கப்பட்ட பட்டியல் லீட்கோட் தீர்வு டிகம்பரஸ்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆப்பிள் கூகிள்
அணி

சிக்கல் டிகம்ப்ரஸ் ரன்-நீள குறியாக்கப்பட்ட பட்டியல் லீட்கோட் தீர்வு உங்களுக்கு வழங்கப்பட்டுள்ளது என்று கூறுகிறது வரிசை அல்லது ஒரு வரிசை கொண்ட திசையன். இந்த வரிசையில் சில குறிப்பிட்ட பிரதிநிதித்துவம் உள்ளது. உள்ளீட்டு வரிசை மற்றொரு வரிசையிலிருந்து உருவாகிறது. மற்றொரு வரிசையை அசல் வரிசை என்று அழைப்போம். இதன் படி உள்ளீட்டு வரிசை உருவாக்கப்பட்டது. அசல் வரிசையைக் கண்டுபிடிக்கும்படி கேட்கப்படுகிறோம். வரிசையில் உள்ள ஒவ்வொரு ஒற்றைப்படை (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 இரண்டு முறை மீண்டும் மீண்டும் செய்யப்படுகிறது. மீண்டும் வெளியீடு சரியானது.

டிகம்பரஸ் ரன்-நீளம் குறியிடப்பட்ட பட்டியல் லீட்கோட் தீர்வுக்கான அணுகுமுறை

சிக்கல் டிகம்ப்ரஸ் ரன்-நீள குறியாக்கப்பட்ட பட்டியல் லீட்கோட் தீர்வு ஒரு நிலையான ஒன்றாகும். மேலும் பல்வேறு நிறுவனங்களால் நடத்தப்படும் பல குறியீட்டு சுற்றுகளில் அடிக்கடி கேட்கப்படுகிறது. அசல் வரிசையை சேமிக்க ஒரு புதிய வரிசையை உருவாக்க வேண்டும் என்பதால் அணுகுமுறை மிகவும் எளிதானது. நாங்கள் வெறுமனே வரிசை அல்லது திசையன் ஒன்றைப் பயன்படுத்துகிறோம், பின்புறத்தில் உறுப்புகளைச் சேர்ப்போம்.

ஒவ்வொரு மறு செய்கைக்கும் பிறகு 2 அலகுகளைத் தாவும் ஒரு ஃபார் லூப்பை நாம் இயக்கலாம். நாங்கள் (அதிர்வெண், மதிப்பு) ஜோடிகளை மட்டுமே கையாளுகிறோம் என்பதை இது உறுதிப்படுத்துகிறது. இப்போது மீண்டும் லூப்பிற்காக ஒரு கூடு கொண்டு, ith குறியீட்டில் உள்ள உறுப்பை திசையனுடன் சேர்க்கிறோம். கொடுக்கப்பட்ட உள்ளீட்டு வரிசையில் i + 1 வது குறியீட்டில் உள்ள உறுப்புப்படி லூப்பிற்காக உள்ளமைவை இயக்குகிறோம்.

டிகம்பரஸ் ரன்-நீள குறியாக்கப்பட்ட பட்டியல் லீட்கோட் தீர்வுக்கான குறியீடு

சி ++ குறியீடு

#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

ஜாவா குறியீடு

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 என்பது வெளியீட்டின் நீளம். வெளியீட்டை நாங்கள் சேமிப்பதால், அதை நாங்கள் திருப்பித் தருகிறோம். விண்வெளியும் அதை ஆக்கிரமித்துள்ளது.