อาร์เรย์สูงสุดจากอาร์เรย์สองอาร์เรย์ที่กำหนดให้มีลำดับเหมือนกัน


ระดับความยาก กลาง
ถามบ่อยใน แอคเซนเจอร์ อเมซอน เดลี ข้อเท็จจริง โฟร์ไคต์ ห้องโอโย Publicis Sapient Zoho
แถว กัญชา

สมมติว่าเรามีจำนวนเต็มสองจำนวน แถว n. ขนาดเดียวกัน อาร์เรย์ทั้งสองสามารถมีตัวเลขทั่วไปได้เช่นกัน คำสั่งปัญหาขอให้สร้างอาร์เรย์ผลลัพธ์ที่มีค่าสูงสุด 'n' จากทั้งสองอาร์เรย์ อาร์เรย์แรกควรได้รับการจัดลำดับความสำคัญ (องค์ประกอบของอาร์เรย์แรกควรปรากฏก่อนในเอาต์พุต) อาร์เรย์เอาต์พุตจะเป็นองค์ประกอบสูงสุดจากทั้งสองอาร์เรย์ที่กำหนด แต่องค์ประกอบทั่วไปควรมาครั้งเดียวและจัดลำดับความสำคัญของอาร์เรย์ก่อน

ตัวอย่าง

Input:

int arr1 [] = {3,7,9,1,4}

int arr2 [] = {2,8,6,5,3}

Output:

{7, 9, 8, 6, 5}

คำอธิบาย:

เนื่องจาก 7, 9 เป็นองค์ประกอบในอาร์เรย์แรกดังนั้นจึงต้องมาก่อนในเอาต์พุต

Input:

int arr1 [] = {9,3,2}

int arr2 [] = {6,4,1}

Output:

{9, 6, 4}

อัลกอริทึมสำหรับอาร์เรย์สูงสุดจากอาร์เรย์ที่กำหนดสองอาร์เรย์ที่มีลำดับเหมือนกัน

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

คำอธิบาย

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

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

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

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

โปรแกรม C ++ สำหรับอาร์เรย์สูงสุดจากอาร์เรย์ที่กำหนดให้สองอาร์เรย์รักษาลำดับเดียวกัน

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;

void makeGreaterFirstArray(int A[], int B[], int n)
{
    vector<int> V1(A, A+n);
    vector<int> V2(B, B+n);
    sort(V1.begin(), V1.end(), greater<int>());
    sort(V2.begin(), V2.end(), greater<int>());

    unordered_map<int, int> MAP;
    int i = 0, j = 0;
    while (MAP.size() < n)
    {
        if (V1[i] >= V2[j])
        {
            MAP[V1[i]]++;
            i++;
        }
        else
        {
            MAP[V2[j]]++;
            j++;
        }
    }
    vector<int> output;
    for (int i = 0; i < n; i++)
        if (MAP.find(A[i]) != MAP.end())
            output.push_back(A[i]);

    for (int i = 0; i < n; i++)
        if (MAP.find(B[i]) != MAP.end() && MAP[B[i]] == 1)
            output.push_back(B[i]);

    for (int i = 0; i < n; i++)
        cout << output[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    makeGreaterFirstArray(arr1, arr2, n);
    return 0;
}
7 9 8 6 5

โปรแกรม Java สำหรับอาร์เรย์สูงสุดจากอาร์เรย์ที่กำหนดให้สองอาร์เรย์รักษาลำดับเดียวกัน

import java.util.Collections;
import java.util.Vector;
import java.util.HashMap;
import java.util.Arrays;
import java.util.stream.Collectors;

class findsubarray
{
    public static void makeGreaterFirstArray(int []A, int []B, int n)
    {
        Vector<Integer> V1 = new Vector<>();
        Vector<Integer> V2 = new Vector<>();

        Integer[] I1 = Arrays.stream( A ).boxed().toArray( Integer[]::new );
        Integer[] I2 = Arrays.stream( B ).boxed().toArray( Integer[]::new );


        Collections.addAll(V1, I1);
        Collections.addAll(V2, I2);

        Collections.sort(V1, Collections.reverseOrder());
        Collections.sort(V2, Collections.reverseOrder());


        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int i = 0, j = 0;
        while (MAP.size() < n)
        {
            if (V1.get(i) >= V2.get(j))
            {
                if(MAP.containsKey(V1.get(i)))
                {
                    MAP.put(V1.get(i), MAP.get(V1.get(i))+1);
                    i++;
                }
                else
                {
                    MAP.put(V1.get(i),1);
                    i++;
                }
            }
            else
            {
                if(MAP.containsKey(V2.get(j)))
                {
                    MAP.put(V2.get(j), MAP.get(V2.get(j))+1);
                    j++;
                }
                else
                {
                    MAP.put(V2.get(j),1);
                    j++;
                }
            }
        }
        Vector<Integer> output = new Vector<Integer>();

        for (int a = 0; a < n; a++)
            if (MAP.containsKey(A[a]))
                output.add(A[a]);

        for (int b = 0; b < n; b++)
            if (MAP.containsKey(B[b]) && MAP.get(B[b])==1)
                output.add(B[b]);


        System.out.println(output);
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        makeGreaterFirstArray(arr1, arr2, n);
    }
}
[7, 9, 8, 6, 5]

การวิเคราะห์ความซับซ้อนสำหรับอาร์เรย์สูงสุดจากอาร์เรย์ที่กำหนดสองอาร์เรย์ที่รักษาลำดับเดียวกัน

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

O (n บันทึก n) ที่ไหน “ n” คือความยาวของอาร์เรย์

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

O (n) ที่ไหน “ n” คือความยาวของอาร์เรย์