배열 Leetcode 솔루션 섞기

난이도 쉽게
자주 묻는 질문 어도비 벽돌 Apple 블룸버그 게시물에서 구글 Microsoft
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 48

Shuffle the Array Leetcode Solution 문제는 길이 2n의 배열을 제공합니다. 여기서 2n은 정렬 길이는 짝수입니다. 그런 다음 배열을 섞으라는 지시를받습니다. 여기서 셔플 링은 배열을 무작위로 셔플해야한다는 것을 의미하지는 않지만 특정 방법이 표시됩니다. 주어진 배열이 [x1, x2,…, y1, y2,…]로 표현 될 수 있다면 셔플 링은 [x1, y1, x2, y2,…]로 표현됩니다. 따라서 문제는 매우 간단하며 우리가 아무것도 해결할 것으로 기대하지 않습니다. 필요한 시퀀스를 얻기 위해 요소를 교체하는 방법을 찾기 만하면됩니다. 또한 입력에 대한 제약이 하나 있습니다. 입력 요소는 10 ^ 3 미만입니다. 그러나 솔루션에 깊이 들어가기 전에 몇 가지 예를 살펴 보겠습니다.

배열 Leetcode 솔루션 섞기

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

설명 : 출력이 문제에 부과 된 필수 기준을 충족하는지 쉽게 확인할 수 있습니다. x1, x2와 같은 이름을 y3까지 배열 요소에 할당하면. 이제 요소가 [x1, y1, x2, y2, x3, y3] 형식으로 배열 된 것을 볼 수 있습니다.

Shuffle the Array Leetcode 솔루션에 대한 접근 방식

Shuffle the Array Leetcode Solution 문제는 특정 방식으로 배열을 섞도록 요청합니다. 셔플 링 방식은 배열의 마지막 절반 요소를 전반의 요소 사이에 배치하도록 요청합니다. 좀 더 공식적으로 배열 [x1, x2, x3,…, y1, y2, y3,…]은 [x1, y1, x2, y2, x3, y3,… xn, yn]으로 섞이게됩니다. 따라서 추가 공간의 도움으로 문제를 쉽게 해결할 수 있습니다. 그러면 원래 배열과 같은 길이의 새 배열을 간단히 만들 수 있기 때문입니다. 그리고 전반부부터 후반부까지 요소를 밀어냅니다. 이렇게하면 필요한 배열이 완성됩니다.

O (1) 공간에 추가 공간없이 문제를 해결합니다. 바이너리 조작의 도움이 필요합니다. 이 알고리즘은 자주 보이지 않기 때문에 속임수처럼 보일 수 있습니다. 따라서 이러한 문제는 임시 범주에 속합니다. 문제를 해결하는 첫 번째 단계는 전반부와 후반부의 요소를 어떻게 든 후반부에 결합하는 것입니다. 그러나이 결합은 무엇을 의미합니까? 먼저 요소를 후반부에서 왼쪽 (왼쪽 이진 이동)으로 10 비트 이동합니다. 그런 다음 전반부의 요소를 추가하거나 후반부의 요소와 전반부의 요소를 OR로 가져옵니다. 이제 요소가 결합됩니다.

이제 단순히 원래 배열 위로 이동합니다. 반복 할 때마다 2 단계 씩 증가하는 for 루프를 시작합니다. 각 단계에서 우리는 후반부에서 요소를 선택하고이 위치의 요소를 xi, yi로 바꿉니다. 우리는 첫 번째 요소를 얻기 위해 2 ^ 10-1로 후반부에있는 요소의 AND를 먼저 취함으로써 xi, yi를 얻을 수 있습니다. 두 번째 요소의 경우 각 요소를 10 비트 씩 오른쪽으로 이동합니다.

배열 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

자바 코드

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

복잡성 분석

시간 복잡성

의 위에), 배열의 각 요소를 순회하기 때문입니다. 비록 우리가 제공되지만 2n 요소, 시간 복잡도는 여전히 O (N)으로 남아 있습니다.

공간 복잡성

O (1), 알고리즘은 내부 알고리즘입니다. 따라서 공간 복잡성도 일정합니다.

코멘트를 남겨

Translate »
1