ແກ້ໄຂ Array Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe ຈາກຫນາກແອບເປີ Bloomberg ກູໂກ Microsoft
Array

ບັນຫາການແກ້ໄຂ Array Leetcode Solution ໃຫ້ພວກເຮົາມີຄວາມຍາວ 2n. ນີ້ 2n ໝາຍ ເຖິງ ຄຳ ວ່າ the array ຄວາມຍາວແມ່ນແຕ່. ຫຼັງຈາກນັ້ນພວກເຮົາຖືກບອກໃຫ້ຮື້ຖອນຂບວນ. ການຖີ້ມບ່ອນນີ້ບໍ່ໄດ້ ໝາຍ ຄວາມວ່າພວກເຮົາ ຈຳ ເປັນຕ້ອງຖີ້ມຖັງແບບສຸ່ມແຕ່ມີວິທີສະເພາະ. ຖ້າອາເລທີ່ ກຳ ນົດໃຫ້ສາມາດເປັນຕົວແທນເປັນ [x1, x2, …, y1, y2, …] ຈາກນັ້ນການສັ່ນແມ່ນຕົວແທນເປັນ [x1, y1, x2, y2, …]. ສະນັ້ນບັນຫາແມ່ນຂ້ອນຂ້າງຕັ້ງ ໜ້າ ແລະບໍ່ຄາດຫວັງໃຫ້ພວກເຮົາແກ້ໄຂບັນຫາຫຍັງ. ພວກເຮົາພຽງແຕ່ຕ້ອງການຊອກຫາບາງວິທີທີ່ຈະແລກປ່ຽນອົງປະກອບເພື່ອໃຫ້ໄດ້ຕາມ ລຳ ດັບທີ່ຕ້ອງການ. ມັນຍັງມີຂໍ້ ຈຳ ກັດ ໜຶ່ງ ອີກຕໍ່ການປ້ອນຂໍ້ມູນ, ສ່ວນປະກອບປ້ອນຂໍ້ມູນ ໜ້ອຍ ກວ່າ 10 ^ 3. ແຕ່ກ່ອນທີ່ຈະ ດຳ ນ້ ຳ ເລິກເຂົ້າໃນການແກ້ໄຂ, ຂໍໃຫ້ພວກເຮົາຍົກເລິກໃນບາງຕົວຢ່າງ.

ແກ້ໄຂ Array Leetcode Solution

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

ຄຳ ອະທິບາຍ: ພວກເຮົາຢັ້ງຢືນໄດ້ຢ່າງງ່າຍດາຍວ່າຜົນຜະລິດຕອບສະ ໜອງ ໄດ້ຕາມເງື່ອນໄຂທີ່ ກຳ ນົດໄວ້ໃນກົດ ໝາຍ. ຖ້າພວກເຮົາມອບ ໝາຍ ການຕັ້ງຊື່ເຊັ່ນ: x1, x2, ຈົນຮອດ y3 ກັບອົງປະກອບຂອງອາເລ. ພວກເຮົາສາມາດເຫັນໄດ້ວ່າປັດຈຸບັນອົງປະກອບຕ່າງໆໄດ້ຖືກຈັດເປັນແບບ [x1, y1, x2, y2, x3, y3].

ວິທີການແກ້ໄຂ Array Leetcode Solution

ບັນຫາ Shuffle the Array Leetcode Solution ຂໍໃຫ້ມີການຂູດຂບວນໃນລັກສະນະສະເພາະ. ແຟຊັ່ນທີ່ສັ່ນສະເທືອນຂໍໃຫ້ພວກເຮົາວາງອົງປະກອບເຄິ່ງສຸດທ້າຍຂອງອາເລລະຫວ່າງອົງປະກອບຂອງເຄິ່ງ ທຳ ອິດ. ຢ່າງເປັນທາງການແລ້ວ, ອາເລ [x1, x2, x3, …, y1, y2, y3, …] ແມ່ນຈະຖືກດັດແປງເປັນ [x1, y1, x2, y2, x3, y3, … xn, yn]. ສະນັ້ນຄົນເຮົາສາມາດແກ້ໄຂບັນຫາໄດ້ຢ່າງງ່າຍດາຍດ້ວຍຄວາມຊ່ວຍເຫລືອຂອງພື້ນທີ່ເພີ່ມເຕີມ ເພາະວ່າຫຼັງຈາກນັ້ນພວກເຮົາພຽງແຕ່ສາມາດສ້າງແຖວ ໃໝ່ ຂອງຄວາມຍາວດຽວກັນກັບຂອງເດີມ. ແລະຍູ້ອົງປະກອບຈາກເຄິ່ງ ທຳ ອິດຫຼັງຈາກນັ້ນເຄິ່ງທີ່ສອງ. ວິທີນີ້ພວກເຮົາຈົບລົງດ້ວຍຂບວນທີ່ ຈຳ ເປັນ.

ເພື່ອແກ້ໄຂບັນຫາໂດຍບໍ່ມີພື້ນທີ່ເພີ່ມເຕີມທີ່ຢູ່ໃນຊ່ອງ O (1). ພວກເຮົາຕ້ອງການຄວາມຊ່ວຍເຫຼືອຈາກການ ໝູນ ໃຊ້ຄູ່. ນີ້ອາດເບິ່ງຄືວ່າເປັນການຫຼອກລວງເພາະວ່າສູດການຄິດໄລ່ເຫລົ່ານີ້ບໍ່ຄ່ອຍເຫັນເລື້ອຍໆ. ດັ່ງນັ້ນບັນຫາເຫລົ່ານີ້ຈະຕົກຢູ່ພາຍໃຕ້ປະເພດຂອງການໂຄສະນາ. ຂັ້ນຕອນ ທຳ ອິດໃນການແກ້ໄຂບັນຫາແມ່ນການສົມທົບອົງປະກອບຕ່າງໆຈາກເຄິ່ງ ທຳ ອິດແລະເຄິ່ງ ໜຶ່ງ ເຂົ້າໃນເຄິ່ງທີ່ສອງ. ແຕ່ວ່າ COMBINE ນີ້ ໝາຍ ຄວາມວ່າແນວໃດ? ພວກເຮົາປ່ຽນອົງປະກອບຈາກເຄິ່ງ ທຳ ອິດໄປທາງຊ້າຍ (ເລື່ອນໄບນາລີເບື້ອງຊ້າຍ) ໂດຍ 10 ບາດ. ຫຼັງຈາກນັ້ນບໍ່ວ່າພວກເຮົາຈະເພີ່ມສ່ວນປະກອບຂອງເຄິ່ງ ທຳ ອິດຫຼືພວກເຮົາເອົາ OR ຂອງອົງປະກອບຂອງເຄິ່ງທີ່ສອງກັບສ່ວນປະກອບຂອງເຄິ່ງ ທຳ ອິດ. ສະນັ້ນດຽວນີ້ອົງປະກອບລວມເຂົ້າກັນແລ້ວ.

ໃນປັດຈຸບັນພຽງແຕ່ traverse ຫຼາຍກວ່າຂບວນຕົ້ນສະບັບ. ພວກເຮົາເລີ່ມຕົ້ນສໍາລັບການ loop ທີ່ເພີ່ມ 2 ຂັ້ນຕອນໃນແຕ່ລະ iteration. ໃນແຕ່ລະບາດກ້າວພວກເຮົາເລືອກເອົາອົງປະກອບ ໜຶ່ງ ຈາກເຄິ່ງທີ່ສອງແລະທົດແທນອົງປະກອບທີ່ຢູ່ສະຖານທີ່ເຫຼົ່ານີ້ດ້ວຍສັນຍາ, Yi. ພວກເຮົາສາມາດໄດ້ຮັບສັນຍາ, yi ໂດຍການເອົາຄັ້ງ ທຳ ອິດແລະຂອງທາດໃນເຄິ່ງທີ່ສອງດ້ວຍ 2 ^ 10-1 ເພື່ອໃຫ້ໄດ້ສ່ວນປະກອບ ທຳ ອິດ. ຄືກັບອົງປະກອບທີສອງ, ພວກເຮົາປ່ຽນສິດແຕ່ລະອົງປະກອບລົງ 10 ບິດ.

ລະຫັດ ສຳ ລັບ Shuffle the Array Leetcode Solution

ລະຫັດ 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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (N), ນັບຕັ້ງແຕ່ພວກເຮົາ traverse ແຕ່ລະອົງປະກອບຂອງຂບວນການ. ເຖິງແມ່ນວ່າພວກເຮົາໄດ້ຮັບການສະ ໜອງ ໃຫ້ 2n ອົງປະກອບ, ຄວາມສັບສົນເວລາຍັງຄົງເປັນ O (N).

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (1), ສູດການຄິດໄລ່ແມ່ນວິທີແກ້ໄຂໃນສະຖານທີ່. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນຍັງຄົງທີ່.