ขยายองค์ประกอบให้ใหญ่ที่สุดโดยใช้อาร์เรย์อื่น  


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน fanatics โฟร์ไคต์
แถว กัญชา การเรียงลำดับ

สมมติว่าเราให้อาร์เรย์จำนวนเต็มสองตัวที่มีขนาดเท่ากัน n อาร์เรย์ทั้งสองประกอบด้วยจำนวนบวก คำสั่งปัญหาขอให้ขยายอาร์เรย์แรกให้ใหญ่ที่สุดโดยใช้องค์ประกอบอาร์เรย์ที่สองทำให้อาร์เรย์ที่สองเป็นลำดับความสำคัญ (องค์ประกอบของอาร์เรย์ที่สองควรปรากฏเป็นอันดับแรกในเอาต์พุต) อาร์เรย์ที่สร้างขึ้นควรมี n องค์ประกอบที่เป็นเอกลักษณ์ แต่ยิ่งใหญ่ที่สุดของอาร์เรย์ทั้งสอง

ตัวอย่าง  

arr1[] = {3,7,9,1,4}
arr2[] = {2,8,6,5,3}
{8, 6, 5, 7, 9}
arr1[] = {9,3,2}
arr2[] = {6,4,1}
{6, 4, 9}

ขั้นตอนวิธี  

  1. สร้าง แถว ขนาด 2 * n.
  2. ขั้นแรกให้เก็บองค์ประกอบอาร์เรย์ที่สองไว้ในอาร์เรย์ที่สร้างขึ้นจากนั้นจึงจัดเก็บองค์ประกอบอาร์เรย์แรก
  3. เรียงลำดับอาร์เรย์ในลำดับที่ไม่น้อยไปหามาก
  4. เก็บค่า n ของอาร์เรย์ไว้ในไฟล์ ชุด.
  5. จัดเรียงตามลำดับที่มาเป็นอินพุตโดยรับ array2 ก่อนและตรวจสอบว่ามีองค์ประกอบอยู่ในชุดหรือไม่และเก็บไว้ในอาร์เรย์ที่สามจาก 0th ดัชนี
  6. ทำซ้ำขั้นตอนข้างต้นสำหรับอาร์เรย์แรก
  7. พิมพ์อาร์เรย์ผลลัพธ์

คำอธิบาย  

เรามีสอง จำนวนเต็ม แถว. เราจำเป็นต้องขยายอาร์เรย์แรกให้ใหญ่ที่สุดในลักษณะที่อาร์เรย์ที่สร้างขึ้นมีองค์ประกอบอาร์เรย์ที่สองก่อนแล้วจึงเป็นอาร์เรย์แรก ควรมีไฟล์ n องค์ประกอบที่เป็นเอกลักษณ์และยิ่งใหญ่ที่สุดจากอาร์เรย์ทั้งสอง ควรรักษาลำดับไว้คือถ้าองค์ประกอบมาก่อนก็ควรมาก่อนในอาร์เรย์ที่สอง ในการแก้ปัญหานี้ให้สร้างอาร์เรย์ขนาด 2 * n เนื่องจากเรามีอาร์เรย์ที่กำหนดเป็นขนาด n และเราเพียงแค่ต้องจัดเก็บองค์ประกอบของอาร์เรย์ทั้งสอง

ดูสิ่งนี้ด้วย
สร้างตัวเลขขั้นต่ำจากลำดับที่กำหนด

เก็บองค์ประกอบของอาร์เรย์ที่สองไว้ในอาร์เรย์ที่เราสร้างขึ้นก่อนจากนั้นจึงจัดเก็บองค์ประกอบของอาร์เรย์แรกไปยังอาร์เรย์ที่สร้างขึ้น เรากำลังทำสิ่งนี้เพราะเราจะแทรกค่าทั้งหมดของอาร์เรย์ที่สร้างขึ้นเพื่อตั้งค่า เพราะในการแก้รหัสนี้เราจะใช้ชุด หลังจากใส่ค่าทั้งหมดของอาร์เรย์ที่สร้างลงในชุดแล้ว เราจะเรียงอาร์เรย์แบบไม่เรียงลำดับจากน้อยไปหามาก

เราจะสร้างตำแหน่งใน Set เพื่อแทรกค่าจากอาร์เรย์สูงสุด n ครั้ง N ครั้งมีไว้สำหรับเรามีอาร์เรย์ที่จัดเรียงไว้แล้วในลำดับที่ไม่ใช่จากน้อยไปหามากเราแค่ต้องการองค์ประกอบ n ตัวแรกในตอนนี้เพื่อดำเนินการกับมัน หลังจากการแทรก Set เราจะมีค่า n ที่ยิ่งใหญ่ที่สุดในชุด ตอนนี้เราจำเป็นต้องจัดเรียงค่านั้นตามลำดับเมื่อเข้ามาดังนั้นเราจะสำรวจอาร์เรย์เป็นลำดับที่สองเนื่องจากอาร์เรย์นั้นเป็นลำดับความสำคัญของเรา ดังนั้นหากเราพบองค์ประกอบใด ๆ ของอาร์เรย์ที่สองอยู่ในชุด เราจะอัปเดตอาร์เรย์ที่สร้างจากตำแหน่งที่ 0 และตรวจสอบอาร์เรย์แรกด้วยและอัปเดตค่าในอาร์เรย์ที่สาม

ตอนนี้อัปเดตค่าของ array3 เป็น array1 และพิมพ์ array1 และนั่นคือวิธีที่เราเพิ่มอาร์เรย์แรกให้มากที่สุดโดยให้อาร์เรย์ที่สองเป็นลำดับความสำคัญ

การดำเนินงาน  

โปรแกรม C ++ สำหรับการขยายองค์ประกอบโดยใช้อาร์เรย์อื่น

#include <iostream>
#include<algorithm>
#include<unordered_set>

using namespace std;

bool compare(int a, int b)
{
    return a > b;
}
void getMaximizeArray(int arr1[], int arr2[], int n)
{
    int arr3[2*n], j = 0;
    for (int i = 0; i < n; i++)
        arr3[j++] = arr1[i];
    for (int i = 0; i < n; i++)
        arr3[j++] = arr2[i];

    unordered_set<int> SET;

    sort(arr3, arr3 + 2 * n, compare);

    int i = 0;
    while (SET.size() != n)
    {
        if (SET.find(arr3[i]) == SET.end())
            SET.insert(arr3[i]);

        i++;
    }
    j = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr2[i]) != SET.end())
        {
            arr3[j++] = arr2[i];
            SET.erase(arr2[i]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr1[i]) != SET.end())
        {
            arr3[j++] = arr1[i];
            SET.erase(arr1[i]);
        }
    }
    for (int i = 0; i < n; i++)
        arr1[i] = arr3[i];
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    getMaximizeArray(arr1, arr2, n);
    printArray(arr1, n);
}
8 6 5 7 9

โปรแกรม Java สำหรับขยายองค์ประกอบโดยใช้อาร์เรย์อื่น

import java.util.HashSet;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.lang.*;

class arrayMaximize
{
    public static void getMaximizeArray(int arr1[], int arr2[], int n)
    {
        int arr3[]=new int[2*n];
        int j = 0;
        for (int i = 0; i < n; i++)
            arr3[j++] = arr1[i];
        for (int i = 0; i < n; i++)
            arr3[j++] = arr2[i];


        Arrays.sort(arr3);

        HashSet<Integer> SET=new HashSet<>();

        int i = (2*n)-1;
        while (SET.size() != n)
        {
            if (!SET.contains(arr3[i]))
                SET.add(arr3[i]);

            i--;
        }


        j = 0;
        for (int a = 0; a < n; a++)
        {
            if (SET.contains(arr2[a]))
            {
                arr3[j++] = arr2[a];
                SET.remove(arr2[a]);
            }
        }

        for (int b = 0; b < n; b++)
        {
            if (SET.contains(arr1[b]))
            {
                arr3[j++] = arr1[b];
                SET.remove(arr1[b]);
            }
        }
        for (int c = 0; c < n; c++)
            arr1[c] = arr3[c];
    }
    public static void printArray(int arr[], int n)
    {
        for (int k = 0; k < n; k++)
            System.out.print(arr[k]+" ");
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        getMaximizeArray(arr1, arr2, n);
        printArray(arr1, n);
    }
}
8 6 5 7 9

การวิเคราะห์ความซับซ้อนเพื่อเพิ่มองค์ประกอบสูงสุดโดยใช้อาร์เรย์อื่น  

ความซับซ้อนของเวลา

O (n * บันทึก n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์

ดูสิ่งนี้ด้วย
ย้อนกลับรายการที่เชื่อมโยง

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์

อ้างอิง