ערבב את פתרון ה- Array Leetcode


רמת קושי קַל
נשאל לעתים קרובות Adobe תפוח עץ בלומברג Google מיקרוסופט
מערך

הבעיה ערבב את פתרון ה- Array Leetcode מספק לנו מערך באורך 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]

הסבר: אנו מוודאים בקלות כי התפוקה עומדת בקריטריונים הנדרשים כפי שמוטלים בבעיה. אם נקצה שמות כגון x1, x2, עד y3 לאלמנטים של המערך. אנו יכולים לראות שהאלמנטים מסודרים כעת בצורה [x1, y1, x2, y2, x3, y3].

גישה לערבב את פתרון ה- Array Leetcode

הבעיה ערבב את פתרון ה- Array Leetcode מבקש לדשדש את המערך באופן ספציפי. האופנה המדשדשת מבקשת מאיתנו למקם את האלמנטים האחרונים של המערך בין האלמנטים של המחצית הראשונה. באופן רשמי יותר, מערך [x1, x2, x3, ..., y1, y2, y3, ...] אמור להיות מדשדש כ- [x1, y1, x2, y2, x3, y3, ... xn, yn]. כך שאפשר לפתור את הבעיה בקלות בעזרת שטח נוסף. כי אז אנחנו יכולים פשוט ליצור מערך חדש באותו אורך כמו זה המקורי. ודחפו את האלמנטים מהמחצית הראשונה ואז מהמחצית השנייה. בדרך זו אנו מגיעים למערך הנדרש.

כדי לפתור את הבעיה ללא שום מרחב נוסף שנמצא במרחב O (1). עלינו להיעזר במניפולציה בינארית. זה אולי נראה כמו טריק מכיוון שאלגוריתמים אלה לא נראים לעיתים קרובות מאוד. לפיכך בעיות אלה נופלות בקטגוריית אד-הוק. הצעד הראשון לפתרון הבעיה הוא איכשהו לשלב בין האלמנטים מהמחצית הראשונה והשנייה למחצית השנייה. אבל מה המשמעות של COMBINE זה? תחילה מעבירים את האלמנטים מהמחצית השנייה שמאלה (משמרת בינארית שמאלית) ב -10 ביטים. ואז או שנוסיף את האלמנטים של המחצית הראשונה או ניקח את OR של האלמנטים של המחצית השנייה עם האלמנטים של המחצית הראשונה. אז עכשיו האלמנטים משולבים.

עכשיו פשוט חצו את המערך המקורי. אנו מתחילים לולאת for שמגדילה 2 שלבים בכל איטרציה. בכל שלב אנו בוחרים אלמנט מהמחצית השנייה ומחליפים את האלמנטים במקומות אלה ב- xi, yi. אנו יכולים להשיג את ה- xi, yi על ידי נטילת ראשון של האלמנטים במחצית השנייה עם 2 ^ 10-1 כדי לקבל את האלמנט הראשון. באשר לאלמנט השני, אנו משנים נכון כל אלמנט ב -10 ביטים.

קוד לערבב את פתרון ה- 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

קוד ג'אווה

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), האלגוריתם הוא אלגוריתם במקום. כך גם מורכבות החלל קבועה.