다른 배열에서 정의한 순서에 따라 배열 정렬

난이도 쉽게
자주 묻는 질문 아마존 Microsoft SAP 연구소 Snapchat Yahoo 조호 (Zoho)
배열 수색 정렬조회수 40

문제 정책

두 가지가 주어집니다 배열 of 정수 arr1 [] 및 arr2 []. "다른 어레이에서 정의한 순서에 따라 어레이 정렬"문제는 종류 첫 번째 배열은 두 번째 배열에 따라 배열되므로 첫 번째 배열의 숫자는 arr2 []의 모든 값에서 상대적으로 정렬됩니다. 그리고 두 번째 배열에없는 첫 번째 배열의 요소는 정렬 된 방식으로 배열의 끝에 삽입됩니다.

arr1[] = { 2,1,2,5,1,3,6,8,8 }

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

설명

A1은 A2에 따라 정렬됩니다.

다른 배열에서 정의한 순서에 따라 배열 정렬

 

다른 배열에서 정의한 순서에 따라 배열을 정렬하는 알고리즘

1. Sort the array using the qsort method or comparator interface.
2. Search the value in arr2[] and find its index value.
3. Check if
  1. Both of the returned value is -1 if true then return the difference between the returned value.
  2. If one of the first returned values is -1 if true then return the -1.
  3. If the second returned value is -1, then return 1.
4. Else return the value of the difference of the input value.
5. Print the sorted array.

설명

우리는 두 가지를 정수 배열. 그런 다음 우리는 종류 두 번째 배열에 따른 첫 번째 배열. 배열 중 하나는 정렬 할 전체 값을 포함합니다. 그리고 다른 배열에는 첫 번째 배열을 정렬해야하는 순서대로 값이 거의 없습니다. 즉, 두 번째 배열에 (1, 2, 3, 4)로 주어진 숫자가 있습니다. 그리고 우리는 첫 번째 배열에서 모든 1을 검색하고 먼저 배열에서 정렬 된 방식으로 먼저 배치해야합니다. 그런 다음 두 번째 배열에 2가 있습니다. 첫 번째 배열에서 2를 모두 찾은 다음 첫 번째 배열에 넣는 식입니다.

원하는 결과를 찾기 위해 내장 방법을 사용할 것입니다. C ++에서 우리는 큐소트 방법, qsort 방법은 quicksort 알고리즘으로 사용되는 미리 정의 된 방법입니다. 목록을 정렬하는 가장 빠른 알고리즘 중 하나입니다. 그리고 Java에서는 Comparator 인터페이스를 사용하여 두 번째 배열에 따라 배열을 정렬합니다. 이 메서드는 두 가지 값을 선택합니다. 비교를 위해 두 번째로 배열에서 검색하기 위해 해당 값을 전달합니다. 두 번째가 배열에 존재하면 두 값 모두에 대한 인덱스를 반환하고 존재하지 않으면 값 -1을 반환합니다.

우리는 몇 가지 조건을 만들었습니다. 반환 된 값이 모두 양수인 경우. 그런 다음 반환 된 값의 차이를 반환합니다. 첫 번째 값만 양수이면 -1을 반환합니다. 그렇지 않으면 두 번째 값만 양수이면 1을 반환합니다. 조건이 충족되지 않으면 첫 번째 배열에서 선택한 값의 차이를 반환합니다. 모든 비교가 끝나면 배열이 정렬됩니다. 마지막으로 정렬 된 배열을 인쇄합니다.

암호

다른 배열에서 정의한 순서에 따라 배열을 정렬하는 C ++ 코드

#include <stdio.h>
#include<iostream>

using namespace std;

int Arr2[4];

int size = 4;

int searchElement(int key)
{
    int i;
    for (i = 0; i < size; i++)
        if (Arr2[i] == key)
            return i;
    return -1;
}

int compareValuesFromArray(const void* a, const void* b)
{
    int eleIndex1 = searchElement(*(int*)a);
    int eleIndex2 = searchElement(*(int*)b);
    if (eleIndex1 != -1 && eleIndex2 != -1)
        return eleIndex1 - eleIndex2;
    else if (eleIndex1 != -1)
        return -1;
    else if (eleIndex2 != -1)
        return 1;
    else
        return (*(int*)a - *(int*)b);
}

void sortAccAnotherArray(int A1[], int size1)
{
    qsort(A1, size1, sizeof(int), compareValuesFromArray);
}

int main()
{
    int Arr1[] = {1,4,2,4,6,4,7,2,2,3 };
    int Arr2[]= {1,2,3,4};
    int n = sizeof(Arr1) / sizeof(Arr1[0]);

    sortAccAnotherArray(Arr1, n);

    for (int i = 0; i <n; i++)
        printf("%d ", Arr1[i]);
    return 0;
}
1 2 2 2 3 4 4 4 6 7

다른 배열에서 정의한 순서에 따라 배열을 정렬하는 Java 코드

import java.util.*;
import java.util.Arrays;

class SortAnArray
{
    private static int Arr1[] = { 1,4,2,4,6,4,7,2,2,3};
    private static int Arr2[]= {1,2,3,4};

    private static int size = Arr2.length;

    public static int searchElement(int key)
    {
        int i;
        for (i = 0; i < size; i++)
            if (Arr2[i] == key)
                return i;
        return -1;
    }

    public static void sortAccAnotherArray(int A1[], int size1)
    {
        Integer[]sortedArr = Arrays.stream(A1).boxed().toArray(Integer[]::new);

        Arrays.sort(sortedArr, new Comparator<Integer>()
        {
            public int compare(Integer o1, Integer o2)
            {

                int a = o1.intValue();
                int b = o2.intValue();

                int eleIndex1 = searchElement(a);
                int eleIndex2 = searchElement(b);

                if (eleIndex1 != -1 && eleIndex2 != -1)
                    return eleIndex1 - eleIndex2;
                else if (eleIndex1 != -1)
                    return -1;
                else if (eleIndex2 != -1)
                    return 1;
                else
                    return (a - b);
            }
        });
        int[] finalArr = Arrays.stream(sortedArr).mapToInt(Integer::intValue).toArray();
        System.out.println(Arrays.toString(finalArr));
    }

    public static void main(String [] args)
    {

        int n = Arr1.length;

        sortAccAnotherArray(Arr1, n);
    }

}

[1, 2, 2, 2, 3, 4, 4, 4, 6, 7]

복잡성 분석

시간 복잡성

O (mn Logm) 어디에 "엠" arr1 & "엔" arr2의 길이입니다. qsort (정렬 알고리즘)를 사용했기 때문에. 우리는 O (n log n) 인자. 여기서 검색은 선형 검색을 사용하여 수행됩니다. 그렇게하는 대신 시간 복잡성을 더욱 줄여주는 HashMap을 쉽게 사용할 수있었습니다.

공간 복잡성

O (log n), 어디에 "엠""엔" Arr1 및 Arr2의 길이입니다. 빠른 정렬을 사용하여 정렬을 수행했기 때문에 공간 복잡성이 그 때문입니다. 그러나 전체적으로 프로그램은 O (N + M).

Translate »