차례
문제 정책
두 가지가 주어집니다 배열 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).
