Array Leetcode шийдлийг холино


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Apple-ийн Bloomberg Google-ийн Microsoft-
Array

Array Leetcode Solution-ийг холих нь бидэнд 2n урттай массивыг өгдөг. Энд 2n нь массив урт нь тэгш байна. Дараа нь бид массивыг холих хэрэгтэй гэж хэлсэн. Энд холих нь массивыг санамсаргүйгээр холих хэрэгтэй гэсэн үг биш боловч тодорхой арга замыг харуулсан болно. Хэрэв өгөгдсөн массивыг [x1, x2,…, y1, y2,…] гэж төлөөлж болох юм бол холих нь [x1, y1, x2, y2,…] хэлбэрээр илэрхийлэгдэнэ. Тиймээс асуудал нэлээд урагшаа байгаа тул бид юу ч шийдэхгүй гэж найдаж байна. Шаардлагатай дарааллыг олж авахын тулд элементүүдийг хооронд нь солих зарим арга замыг хайж олох шаардлагатай байна. Түүнчлэн оролтын хувьд нэг хязгаарлалт байдаг бөгөөд оролтын элементүүд 10 ^ 3-аас бага байна. Гэхдээ шийдэлд гүнзгий орохоосоо өмнө цөөн хэдэн жишээг авч үзье.

Array Leetcode шийдлийг холино

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

Тайлбар: Асуудалд үндэслэн гаргалт нь шаардлагатай шалгуурыг хангаж байгааг бид хялбархан шалгаж байна. Хэрэв бид массивын элементүүдэд y1 хүртэл x2, x3 гэх мэт нэр өгөх юм бол. Одоо элементүүд [x1, y1, x2, y2, x3, y3] загвараар байрласан байгааг бид харж байна.

Array Leetcode шийдлийг холих арга

Array Leetcode Solution-ийг холих асуудал нь массивыг тодорхой байдлаар холихыг шаарддаг. Холих загвар нь массивын сүүлийн хагас элементүүдийг эхний хагасын элементүүдийн хооронд байрлуулахыг биднээс хүсдэг. Илүү албан ёсоор [x1, x2, x3,…, y1, y2, y3,…] массивыг [x1, y1, x2, y2, x3, y3,… xn, yn] гэж холих хэрэгтэй. Тиймээс нэмэлт зайны тусламжтайгаар асуудлыг хялбархан шийдвэрлэх боломжтой. Учир нь дараа нь бид анхныхтайгаа ижил урттай шинэ массив үүсгэх боломжтой. Эхний хагасаас хоёрдугаар хагасаас элементүүдийг түлхэх хэрэгтэй. Ингэснээр бид шаардлагатай массивыг дуусгах болно.

O (1) зайнд байгаа нэмэлт зайгүйгээр асуудлыг шийдвэрлэх. Бид хоёртын хувилбараас тусламж авах хэрэгтэй. Эдгээр алгоритмууд төдийлөн харагддаггүй тул энэ нь заль мэх мэт санагдаж магадгүй юм. Тиймээс эдгээр асуудал нь түр зуурын гэсэн ангилалд багтдаг. Асуудлыг шийдэх эхний алхам бол эхний ба хоёрдугаар хагасаас хоёр дахь хагас хүртэлх элементүүдийг ямар нэгэн байдлаар нэгтгэх явдал юм. Гэхдээ энэ КОМБАЙН гэдэг нь юу гэсэн үг вэ? Бид эхлээд элементүүдийг хоёр дахь хагасаас зүүн тийш (зүүн хоёртын шилжилт) 10 битээр шилжүүлнэ. Дараа нь бид эхний хагасын элементүүдийг нэмнэ эсвэл хоёрдугаар хагасын элементүүдийг эхний хагасын элементүүдтэй хамт авна. одоо элементүүдийг нэгтгэж байна.

Одоо анхны массивыг дайран өнгөрөөдөг. Давталт бүрт 2 алхамыг нэмэгдүүлдэг for for давталтыг эхлүүлдэг. Алхам бүрт бид хоёрдугаар хагасаас элемент сонгож, эдгээр газруудын элементүүдийг xi, yi-ээр солино. Бид эхний элементийг авахын тулд 2 ^ 10-1-ээр 10-р хагаст орсон элементүүдийн AND хэсгийг аваад xi, yi-г авах боломжтой. Хоёрдахь элементийн хувьд бид элемент бүрийг XNUMX битээр зөв шилжүүлдэг.

Array Leetcode шийдлийг холих код

C ++ код

#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 код

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), Бид массивын элемент бүрийг дайран өнгөрдөг тул. Хэдийгээр бидэнд хангаж өгдөг 2n цаг хугацааны нарийн төвөгтэй байдал нь O (N) хэвээр байна.

Сансрын нарийн төвөгтэй байдал

O (1), алгоритм нь газар дээр нь байрлуулсан алгоритм юм. Тиймээс сансрын нарийн төвөгтэй байдал нь мөн тогтмол байдаг.