សាប់ដំណោះស្រាយអារេឡេឡេកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ក្រុមហ៊ុន google ក្រុមហ៊ុន Microsoft
អារេ

បញ្ហាសាប់ដំណោះស្រាយអារេឡេសកូដកូដផ្តល់ឱ្យយើងនូវអារេនៃប្រវែង 2 អ៊ី។ នៅទីនេះ 2n សំដៅទៅលើឯកសារ អារេ ប្រវែងគឺសូម្បីតែ។ បន្ទាប់មកយើងត្រូវបានគេប្រាប់ឱ្យរុះរើអារេ។ នៅទីនេះការសាប់មិនមានន័យថាយើងត្រូវច្របាច់អារេដោយចៃដន្យទេប៉ុន្តែវិធីជាក់លាក់មួយត្រូវបានបង្ហាញ។ ប្រសិនបើអារេដែលបានផ្តល់អោយអាចត្រូវបានតំណាងដូចជា [x1, x2, …, y1, y2, …] បន្ទាប់មកការរុះរើត្រូវបានតំណាងថាជា [x1, y1, x2, y2, …] ។ ដូច្នេះបញ្ហាគឺត្រង់ត្រង់ហើយមិនសង្ឃឹមថាយើងអាចដោះស្រាយបានទេ។ យើងត្រូវបានទាមទារឱ្យរកវិធីដើម្បីផ្លាស់ប្តូរធាតុដើម្បីទទួលបានលំដាប់ដែលត្រូវការ។ វាក៏មានឧបសគ្គមួយផងដែរលើធាតុបញ្ចូលធាតុបញ្ចូលតិចជាង 10 ^ 3 ។ ប៉ុន្តែមុនពេលមុជជ្រៅទៅក្នុងដំណោះស្រាយសូមឱ្យយើងធ្វើរង្វិលជុំនៅឧទាហរណ៍មួយចំនួន។

សាប់ដំណោះស្រាយអារេឡេឡេកូដ

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

ការពន្យល់ៈយើងផ្ទៀងផ្ទាត់យ៉ាងងាយថាលទ្ធផលទទួលបាននូវលក្ខណៈវិនិច្ឆ័យដែលត្រូវការដូចមានចែងក្នុងបញ្ហា។ ប្រសិនបើយើងដាក់ឈ្មោះដូចជា x1, x2, រហូតដល់ y3 ទៅធាតុនៃអារេ។ យើងអាចមើលឃើញថាធាតុត្រូវបានរៀបចំតាមលំដាប់ [x1, 1, x 2, y2, x3, y3] ។

វិធីសាស្រ្តក្នុងការសាប់ដំណោះស្រាយអារេឡេឡេកូដ

បញ្ហាសាប់ដំណោះស្រាយអារេឡេអាកូដកូដស្នើឱ្យរុះរើអារេតាមលក្ខណៈជាក់លាក់។ ម៉ូដសាប់ស្នើឱ្យយើងដាក់ធាតុពាក់កណ្តាលចុងក្រោយនៃអារេរវាងធាតុនៃពាក់កណ្តាលទីមួយ។ ជាផ្លូវការបន្ថែមទៀតអារេ [x1, x2, x3, …, y1, y2, y3, …] នឹងត្រូវបានផ្លាស់ប្តូរដូចជា [x1, y1, x2, y2, x3, y3, … xn, yn] ។ ដូច្នេះមនុស្សម្នាក់អាចដោះស្រាយបញ្ហាបានយ៉ាងងាយស្រួលដោយមានជំនួយពីកន្លែងបន្ថែម។ ពីព្រោះពេលនោះយើងអាចបង្កើតអារេថ្មីមួយដែលមានប្រវែងដូចគ្នានឹងដើមមួយ។ ហើយរុញធាតុពីពាក់កណ្តាលទីមួយបន្ទាប់មកពាក់កណ្តាលទីពីរ។ វិធីនេះយើងបញ្ចប់ដោយអារេដែលត្រូវការ។

ដើម្បីដោះស្រាយបញ្ហាដោយមិនចាំបាច់មានកន្លែងទំនេរបន្ថែមដែលមាននៅក្នុងចន្លោះអូ (១) ។ យើងត្រូវទទួលជំនួយពីឧបាយកល។ នេះមើលទៅដូចជាល្បិចពីព្រោះក្បួនដោះស្រាយទាំងនេះមិនត្រូវបានគេមើលឃើញញឹកញាប់ទេ។ ដូច្នេះបញ្ហាទាំងនេះស្ថិតនៅក្រោមប្រភេទនៃអាដហុក។ ជំហានដំបូងដើម្បីដោះស្រាយបញ្ហាគឺត្រូវផ្សំធាតុពីពាក់កណ្តាលទីមួយនិងទីពីរចូលទៅក្នុងពាក់កណ្តាលទីពីរ។ ប៉ុន្តែតើ COMBINE នេះមានន័យយ៉ាងដូចម្តេច? ដំបូងយើងប្តូរធាតុពីពាក់កណ្តាលទីពីរទៅខាងឆ្វេង (ការផ្លាស់ប្តូរគោលពីរខាងឆ្វេង) ដោយ ១០ ប៊ីត។ បន្ទាប់មកយើងបន្ថែមធាតុនៃពាក់កណ្តាលទីមួយឬយើងយក OR នៃធាតុនៃពាក់កណ្តាលទីពីរជាមួយនឹងធាតុនៃពាក់កណ្តាលទីមួយ។ ដូច្នេះឥឡូវនេះធាតុត្រូវបានបញ្ចូលគ្នា។

ឥឡូវនេះគ្រាន់តែឆ្លងកាត់អារេដើម។ យើងចាប់ផ្តើមរង្វិលជុំដែលបង្កើន 2 ជំហានក្នុងការនិយាយឡើងវិញ។ នៅជំហាននីមួយៗយើងជ្រើសរើសយកធាតុមួយពីពាក់កណ្តាលទីពីរហើយជំនួសធាតុនៅកន្លែងទាំងនេះដោយប្រើ xi, yi ។ យើងអាចទទួលបានការចុះបញ្ជីយីដោយទទួលយកធាតុទីមួយនៅពាក់កណ្តាលទីពីរជាមួយ 2 ^ 10-1 ដើម្បីទទួលបានធាតុដំបូង។ ចំពោះធាតុទី ២ យើងប្តូរស្តាំធាតុនីមួយៗ ១០ ប៊ីត។

លេខកូដសំរាប់សាប់ដំណោះស្រាយអារេឡេសកូដ

លេខកូដ 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

កូដចាវ៉ា

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) ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ក្បួនដោះស្រាយគឺជាក្បួនដោះស្រាយនៅនឹងកន្លែង។ ដូច្នេះភាពស្មុគស្មាញនៃលំហរក៏មានថេរដែរ។