Array Leetcode həllini qarışdırın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic alma Bloomberg google microsoft
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 33

Dizini qarışdırmaq Leetcode Solution problemi bizə 2n uzunluqlu bir sıra verir. Burada 2n array uzunluq bərabərdir. Ardından serialı qarışdırmamız lazımdır. Burada qarışdırmaq o demək deyil ki, biz təsadüfi şəkildə qarışıqlığı qarışdırmalıyıq, ancaq müəyyən bir yol göstərilib. Verilən massiv [x1, x2,…, y1, y2,…] şəklində təmsil oluna bilərsə, qarışdırma [x1, y1, x2, y2,…] şəklində təmsil olunur. Beləliklə problem olduqca düzdür və bir şey həll etməyimizi gözləmir. Lazımi ardıcıllığı əldə etmək üçün elementləri dəyişdirmək üçün bir yol tapmağımız tələb olunur. Giriş üzərində bir məhdudiyyət də var, giriş elementləri 10 ^ 3-dən azdır. Ancaq həllin dərinliyinə dalmadan əvvəl, bir neçə nümunəyə nəzər salaq.

Array Leetcode həllini qarışdırınPin

nums = [2,5,1,3,4,7], n = 3
[2,3,5,4,1,7]

İzahat: Çıxışın problemdə qoyulduğu kimi tələb olunan meyarlara cavab verdiyini asanlıqla doğrulayırıq. Dizinin elementlərinə y1-ə qədər x2, x3 kimi ad qoysaq. Elementlərin indi [x1, y1, x2, y2, x3, y3] qaydasında yerləşdiyini görə bilərik.

Array Leetcode həllini qarışdırmaq üçün yanaşma

Məsələ qarışdırmaq Leetcode Solution problemi xüsusi bir şəkildə qarışdırmaq isteyir. Qarışıqlıq modu, serialın son yarısı elementlərini birinci yarının elementləri arasında yerləşdirməyimizi xahiş edir. Daha rəsmi olaraq [x1, x2, x3,…, y1, y2, y3,…] bir sıra [x1, y1, x2, y2, x3, y3,… xn, yn] kimi qarışdırılmalıdır. Beləliklə, əlavə yerin köməyi ilə problemi asanlıqla həll etmək olar. Çünki o zaman sadəcə orijinalınki ilə eyni uzunluqda yeni bir sıra yarada bilərik. Və ilk yarıdan sonra ikinci yarıdan elementləri itələyin. Beləliklə, lazımi sıra ilə başa çatırıq.

Problemi O (1) boşluğunda olan əlavə boşluq olmadan həll etmək. İkili manipulyasiyadan kömək almalıyıq. Bu hiylə kimi görünə bilər, çünki bu alqoritmlərə çox az rast gəlinir. Beləliklə, bu problemlər ad-hoc kateqoriyasına aiddir. Problemi həll etmək üçün ilk addım, elementləri birinci və ikinci yarıdan ikinci yarıya birləşdirməkdir. Bəs bu KOMBİN nə deməkdir? Əvvəlcə elementləri ikinci yarıdan sola (sol ikili keçid) 10 bitə keçiririk. Sonra ya birinci yarının elementlərini əlavə edirik, ya da ikinci yarının elementlərini ilk yarının elementləri ilə alırıq. indi elementlər birləşdirilib.

İndi sadəcə orijinal sıra üzərindən keçin. Hər təkrarlamada 2 pillə artıran for döngəsinə başlayırıq. Hər addımda ikinci yarıdan bir element seçirik və bu yerdəki elementləri xi, yi ilə əvəzləyirik. Xi, yi-ni ikinci yarıdakı elementləri AND-ı 2 ^ 10-1 ilə götürərək birinci elementi əldə edə bilərik. İkinci elementə gəldikdə, hər bir elementi 10 bitə doğru dəyişdiririk.

Array qarışdırmaq üçün kod leetcode həll

C ++ kodu

#include <bits/stdc++.h>
using namespace std;

vector<int> shuffle(vector<int>& nums, int n) {
    for(int i=n;i<2*n;i++){
        nums[i] = nums[i]<<10;
        nums[i] |= nums[i-n];
    }
    int z = n;
    for(int i=0;i<2*n;i+=2){
        nums[i] = nums[z] & 1023;
        nums[i+1] = nums[z++] >> 10;
    }
    return nums;
}

int main() {
    vector<int> input = {2,5,1,3,4,7};
    int n = 3;
    vector<int> output = shuffle(input, n);
    for(auto x: output)
        cout<<x<<" ";
}
2 3 5 4 1 7

Java kodu

import java.util.*;
import java.io.*;

class Main {
    private static int[] shuffle(int[] nums, int n) {
        for(int i=n;i<2*n;i++){
            nums[i] = nums[i]<<10;
            nums[i] |= nums[i-n];
        }
        int z = n;
        for(int i=0;i<2*n;i+=2){
            nums[i] = nums[z] & 1023;
            nums[i+1] = nums[z++] >> 10;
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] input = {2,5,1,3,4,7};
        int n = 3;
        int[] output = shuffle(input, n);
        for(int i=0;i<2*n;i++)
            System.out.print(output[i]+" ");
    }
}
2 3 5 4 1 7

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), serialın hər bir elementini keçdiyimiz üçün. Bizə təmin olunsa da 2n elementlər, zaman karmaşıklığı hələ O (N) olaraq qalır.

Kosmik Mürəkkəblik

O (1), alqoritm yerində olan bir alqoritmdir. Beləliklə kosmik mürəkkəblik də sabitdir.

Şərh yaz

Translate »
1