Сортировать массив в соответствии с порядком, определенным другим массивом

01.01.2020Массивы, Поиск, Сортировка

Учитывая два массива A1 [] и A2 [], сортируйте A1 таким образом, чтобы относительный порядок среди элементов был таким же, как в A2. Для элементов, отсутствующих в A2, добавьте их, наконец, в отсортированном порядке.
Пример:

 Input: A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}
       A2[] = {2, 1, 8, 3}
Output: A1[] = {2, 2, 1, 1, 8, 8, 3, 5, 6, 7, 9}

Код должен обрабатывать все случаи, например, количество элементов в A2 [] может быть больше или меньше по сравнению с A1 []. A2 [] может иметь некоторые элементы, которых может не быть в A1 [], и наоборот, также возможно.

Источник : Amazon Интервью | Комплект 110 (в кампусе)

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Метод 1 (Использование сортировки и двоичного поиска)
Пусть размер A1 [] равен m, а размер A2 [] равен n.

Создайте временный массив temp размера m и скопируйте в него содержимое A1 [].
Создайте еще один массив с именем [] и инициализируйте все записи в нем как ложные. visit [] используется для пометки тех элементов в temp [], которые копируются в A1 [].
Сортировать темп []
Инициализируйте выходной индекс ind как 0.
Выполните следующие действия для каждого элемента A2 [i] в A2 []
- Двоичный поиск всех вхождений A2 [i] в temp [], если имеется, затем скопируйте все вхождения в A1 [ind] и увеличьте ind. Также отметьте скопированные элементы, которые посетили []
Скопируйте все не посещенные элементы из temp [] в A1 []

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

// Программа на C ++ для сортировки массива в соответствии с определенным порядком
// другим массивом
#include <bits/stdc++.h>

using namespace std;

// Функция на основе бинарного поиска для поиска индекса вхождения FIRST
// из х в обр []. Если х нет, то он возвращает -1

// То же самое можно сделать с помощью lower_bound
// функция в C ++ STL

int first(int arr[], int low, int high, int x, int n)

{

// Проверка состояния

if (high >= low) {

// Находим средний элемент

int mid = low + (high - low) / 2;

// Проверяем крайний левый элемент

// в левой половине массива

if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)

return mid;

// Если элемент лежит на правой половине

if (x > arr[mid])

return first(arr, (mid + 1), high, x, n);

// Проверяем элемент в левой половине

return first(arr, low, (mid - 1), x, n);

}

// Элемент не найден

return -1;

}

// Сортировка A1 [0..m-1] в порядке, определенном A2 [0..n-1].

void sortAccording(int A1[], int A2[], int m, int n)

{

// временный массив используется для хранения копии A1 [] и посещения []

// используется для отметки посещенных элементов в temp [].

int temp[m], visited[m];

for (int i = 0; i < m; i++) {

temp[i] = A1[i];

visited[i] = 0;

}

// Сортировка элементов по времени

sort(temp, temp + m);

// для индекса вывода, который сортируется A1 []

int ind = 0;

// Рассмотрим все элементы A2 [], найдите их в temp []

// и копировать в A1 [] по порядку.

for (int i = 0; i < n; i++) {

// Найти индекс первого вхождения A2 [i] в temp

int f = first(temp, 0, m - 1, A2[i], m);

// Если нет, не нужно продолжать

if (f == -1)

continue;

// Копируем все вхождения A2 [i] в A1 []

for (int j = f; (j < m && temp[j] == A2[i]); j++) {

A1[ind++] = temp[j];

visited[j] = 1;

}

// Теперь копируем все элементы temp []

// которых нет в A2 []

for (int i = 0; i < m; i++)

if (visited[i] == 0)

A1[ind++] = temp[i];

}

// Сервисная функция для печати массива

void printArray(int arr[], int n)

{

// Итерация в массиве

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

cout << endl;

}

// Код драйвера

int main()

{

int A1[] = { 2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8 };

int A2[] = { 2, 1, 8, 3 };

int m = sizeof(A1) / sizeof(A1[0]);

int n = sizeof(A2) / sizeof(A2[0]);

// Печатает отсортированный массив

cout << "Sorted array is \n";

sortAccording(A1, A2, m, n);

printArray(A1, m);

return 0;

}

Джава

// JAVA-программа для сортировки массива по
// в порядке, определенном другим массивом

import java.io.*;

import java.util.Arrays;

class GFG {

/ * Бинарный поиск на основе функции для поиска

индекс ПЕРВОГО вхождения x в обр [].

Если x отсутствует, то возвращается -1 * /

static int first(int arr[], int low, int high,

int x, int n)

{

if (high >= low) {

/ * (низкий + высокий) / 2; * /

int mid = low + (high - low) / 2;

if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)

return mid;

if (x > arr[mid])

return first(arr, (mid + 1), high,

x, n);

return first(arr, low, (mid - 1), x, n);

}

return -1;

}

// Сортируем A1 [0..m-1] по порядку

// определяется A2 [0..n-1].

static void sortAccording(int A1[], int A2[], int m,

int n)

{

// временный массив используется для хранения копии

// из A1 [] и посещения [] используется для пометки

// посещенные элементы в temp [].

int temp[] = new int[m], visited[] = new int[m];

for (int i = 0; i < m; i++) {

temp[i] = A1[i];

visited[i] = 0;

}

// Сортировка элементов по времени

Arrays.sort(temp);

// для индекса вывода, который сортируется A1 []

int ind = 0;

// Рассмотрим все элементы A2 [], найдем их

// в temp [] и копировать в A1 [] по порядку.

for (int i = 0; i < n; i++) {

// Находим индекс первого вхождения

// из A2 [i] по времени

int f = first(temp, 0, m - 1, A2[i], m);

// Если нет, не нужно продолжать

if (f == -1)

continue;

// Копируем все вхождения A2 [i] в A1 []

for (int j = f; (j < m && temp[j] == A2[i]);

j++) {

A1[ind++] = temp[j];

visited[j] = 1;

}

// Теперь копируем все элементы temp [], которые

// отсутствует в A2 []

for (int i = 0; i < m; i++)

if (visited[i] == 0)

A1[ind++] = temp[i];

}

// Сервисная функция для печати массива

static void printArray(int arr[], int n)

{

for (int i = 0; i < n; i++)

System.out.print(arr[i] + " ");

System.out.println();

}

// Программа драйвера для проверки вышеуказанной функции.

public static void main(String args[])

{

int A1[] = { 2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8 };

int A2[] = { 2, 1, 8, 3 };

int m = A1.length;

int n = A2.length;

System.out.println("Sorted array is ");

sortAccording(A1, A2, m, n);

printArray(A1, m);

}

/ * Этот код предоставлен Никитой Тивари. * /

python3

"" "Программа на Python 3 для сортировки массива
в соответствии с порядком, определенным
другой массив "" "

"" "Функция на основе бинарного поиска, чтобы найти
индекс ПЕРВОГО вхождения x в обр [].
Если x отсутствует, то возвращается -1 "" "

def first(arr, low, high, x, n) :

if (high >= low) :

mid = low + (high - low) // 2; # (низкий + высокий) / 2;

if ((mid == 0 or x > arr[mid-1]) and arr[mid] == x) :

return mid

if (x > arr[mid]) :

return first(arr, (mid + 1), high, x, n)

return first(arr, low, (mid -1), x, n)

return -1

# Сортировать A1 [0..m-1] в соответствии с порядком
# определяется как A2 [0..n-1].

def sortAccording(A1, A2, m, n) :

"" "Массив temp используется для хранения копии

A1 [] и посещенный [] используется пометить

посещенные элементы в temp []. "" "

temp = [0] * m

visited = [0] * m

for i in range(0, m) :

temp[i] = A1[i]

visited[i] = 0

# Сортировать элементы в темп

temp.sort()

# для индекса вывода, который отсортирован A1 []

ind = 0

"" "Рассмотрим все элементы A2 [], найдите

их в temp [] и скопируйте в A1 [] по порядку. "" "

for i in range(0, n) :

# Найти индекс первого вхождения

№ А2 [я] в темп

f = first(temp, 0, m-1, A2[i], m)

# Если нет, не нужно продолжать

if (f == -1) :

continue

# Скопировать все вхождения A2 [i] в A1 []

j = f

while (j<m and temp[j]== A2[i]) :

A1[ind] = temp[j];

ind = ind + 1

visited[j] = 1

j = j + 1

# Теперь скопируйте все элементы temp [], которые

# отсутствует в A2 []

for i in range(0, m) :

if (visited[i] == 0) :

A1[ind] = temp[i]

ind = ind + 1

# Сервисная функция для печати массива

def printArray(arr, n) :

for i in range(0, n) :

print(arr[i], end = " ")

print("")

# Программа драйвера для проверки вышеуказанной функции.

A1 = [2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8]

A2 = [2, 1, 8, 3]

m = len(A1)

n = len(A2)

print("Sorted array is ")

sortAccording(A1, A2, m, n)
printArray(A1, m)

# Этот код предоставлен Никитой Тивари.

C #

// AC # программа для сортировки массива по
// в порядке, определенном другим массивом

using System;

class GFG {

/ * Бинарный поиск на основе функции для поиска

индекс ПЕРВОГО вхождения x в обр [].

Если x отсутствует, то возвращается -1 * /

static int first(int[] arr, int low,

int high, int x, int n)

{

if (high >= low) {

/ * (низкий + высокий) / 2; * /

int mid = low + (high - low) / 2;

if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)

return mid;

if (x > arr[mid])

return first(arr, (mid + 1), high,

x, n);

return first(arr, low, (mid - 1), x, n);

}

return -1;

}

// Сортируем A1 [0..m-1] по порядку

// определяется A2 [0..n-1].

static void sortAccording(int[] A1, int[] A2,

int m, int n)

{

// временный массив используется для хранения копии

// из A1 [] и посещения [] используется для пометки

// посещенные элементы в temp [].

int[] temp = new int[m];

int[] visited = new int[m];

for (int i = 0; i < m; i++) {

temp[i] = A1[i];

visited[i] = 0;

}

// Сортировка элементов по времени

Array.Sort(temp);

// для индекса вывода, который

// отсортировано A1 []

int ind = 0;

// Рассмотрим все элементы A2 [], найти

// их в temp [] и копируем в A1 [] в

// заказ.

for (int i = 0; i < n; i++) {

// Находим индекс первого вхождения

// из A2 [i] по времени

int f = first(temp, 0, m - 1, A2[i], m);

// Если нет, не нужно продолжать

if (f == -1)

continue;

// Копируем все вхождения A2 [i] в A1 []

for (int j = f; (j < m && temp[j] == A2[i]); j++) {

A1[ind++] = temp[j];

visited[j] = 1;

}

// Теперь копируем все элементы temp [], которые

// отсутствует в A2 []

for (int i = 0; i < m; i++)

if (visited[i] == 0)

A1[ind++] = temp[i];

}

// Сервисная функция для печати массива

static void printArray(int[] arr, int n)

{

for (int i = 0; i < n; i++)

Console.Write(arr[i] + " ");

Console.WriteLine();

}

// Программа драйвера для проверки вышеуказанной функции.

public static void Main()

{

int[] A1 = { 2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8 };

int[] A2 = { 2, 1, 8, 3 };

int m = A1.Length;

int n = A2.Length;

Console.WriteLine("Sorted array is ");

sortAccording(A1, A2, m, n);

printArray(A1, m);

}

// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP-программа для сортировки массива по
// в порядке, определенном другим массивом

/ * Функция на основе бинарного поиска для поиска индекса
ПЕРВОГО вхождения x в обр. []. Если х не
присутствует, то возвращает -1 * /

function first(&$arr, $low, $high, $x, $n)

{

if ($high >= $low)

{

$mid = intval($low + ($high - $low) / 2);

if (($mid == 0 || $x > $arr[$mid - 1]) &&

$arr[$mid] == $x)

return $mid;

if ($x > $arr[$mid])

return first($arr, ($mid + 1), $high, $x, $n);

return first($arr, $low, ($mid - 1), $x, $n);

}

return -1;

}

// Сортируем A1 [0..m-1] по порядку
// определяется A2 [0..n-1].

function sortAccording(&$A1, &$A2, $m, $n)

{

// временный массив используется для хранения копии

// из A1 [] иited [] используется для обозначения

// посещенные элементы в temp [].

$temp = array_fill(0, $m, NULL);

$visited = array_fill(0, $m, NULL);

for ($i = 0; $i < $m; $i++)

{

$temp[$i] = $A1[$i];

$visited[$i] = 0;

}

// Сортировка элементов по времени

sort($temp);

$ind = 0; // для индекса вывода, который сортируется A1 []

// Рассмотрим все элементы A2 [], найти

// их в temp [] и копируем в A1 [] по порядку.

for ($i = 0; $i < $n; $i++)

{

// Находим индекс первого вхождения

// из A2 [i] по времени

$f = first($temp, 0, $m - 1, $A2[$i], $m);

// Если нет, не нужно продолжать

if ($f == -1) continue;

// Копируем все вхождения A2 [i] в A1 []

for ($j = $f; ($j < $m &&

$temp[$j] == $A2[$i]); $j++)

{

$A1[$ind++] = $temp[$j];

$visited[$j] = 1;

}

// Теперь копируем все элементы temp [], которые

// нет в A2 []

for ($i = 0; $i < $m; $i++)

if ($visited[$i] == 0)

$A1[$ind++] = $temp[$i];

}

// Сервисная функция для печати массива

function printArray(&$arr, $n)

{

for ($i = 0; $i < $n; $i++)

echo $arr[$i] . " ";

echo "\n";

}

// Код драйвера

$A1 = array(2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8);

$A2 = array(2, 1, 8, 3);

$m = sizeof($A1);

$n = sizeof($A2);

echo "Sorted array is \n";

sortAccording($A1, $A2, $m, $n);

printArray($A1, $m);

// Этот код предоставлен ita_c
?>

Выход:

Sorted array is
2 2 1 1 8 8 3 5 6 7 9

Временная сложность : шаги 1 и 2 требуют времени O (m) . Шаг 3 требует времени O (M * Log M) . Шаг 5 требует времени O (N Log M) . Следовательно, общая сложность времени составляет O (M Log M + N Log M) .

Спасибо Vivek за предложение этого метода.

Метод 2 (Использование самобалансирующегося бинарного дерева поиска )
Мы также можем использовать самобалансировку BST, такую как AVL Tree , Red Black Tree и т. Д. Ниже приведены подробные шаги.

Создайте самобалансировку BST всех элементов в A1 []. В каждом узле BST также следует отслеживать количество появлений ключа и посещенное поле bool, которое инициализируется как false для всех узлов.
Инициализируйте выходной индекс ind как 0.
Выполните следующие действия для каждого элемента A2 [i] в A2 []
1. Найдите A2 [i] в BST, если он есть, затем скопируйте все вхождения в A1 [ind] и увеличьте ind. Также отметьте скопированные элементы, посещенные в узле BST.
Сделайте обход по BST и скопируйте все не посещенные ключи в A1 [].

Сложность времени этого метода такая же, как и в предыдущем методе. Обратите внимание, что в самобалансирующемся бинарном дереве поиска все операции требуют времени входа в систему.

Способ 3 (использовать хеширование)

Перейдите к A1 [], сохраните счетчик каждого числа в HashMap (ключ: число, значение: счетчик числа)
Перейдите через A2 [], проверьте, присутствует ли он в HashMap, если это так, поместите в выходной массив столько раз и удалите число из HashMap.
Отсортируйте оставшиеся числа в HashMap и поместите в выходной массив.

Спасибо Anurag Sigh за предложение этого метода.

Шаги 1 и 2 в среднем занимают O (m + n) время в предположении, что у нас есть хорошая функция хеширования, которая в среднем занимает O (1) время для вставки и поиска. Третий шаг занимает время O (p Log p), где p — количество элементов, оставшихся после рассмотрения элементов A2 [] .

Метод 4 (написание пользовательского метода сравнения)
Мы также можем настроить метод сравнения алгоритма сортировки для решения вышеуказанной проблемы. Например, qsort () в C позволяет нам передавать собственный метод сравнения .

Если num1 и num2 оба находятся в A2, то число с более низким индексом в A2 будет считаться меньшим, чем другие.
Если в A2 присутствует только один из num1 или num2, то это число будет считаться меньшим, чем другое, которого нет в A2.
Если оба не в A2, то естественный порядок будет взят.

Временная сложность этого метода равна O (mnLogm), если мы используем O (nLogn) алгоритм сортировки по временной сложности. Мы можем улучшить временную сложность до O (mLogm) , используя хеширование вместо линейного поиска.

Ниже приведена реализация этого метода.

// Программа на C ++ для сортировки массива в соответствии с определенным порядком
// другим массивом
#include <stdio.h>
#include <stdlib.h>

// A2 сделан здесь глобальным, чтобы его можно было сравнить с помощью compareByA2 ()
// Синтаксис qsort () позволяет сравнивать только два параметраByA2 ()

int A2[5];

// размер A2 []

int size = 5;

int search(int key)

{

int i = 0, idx = 0;

for (i = 0; i < size; i++)

if (A2[i] == key)

return i;

return -1;

}

// Пользовательский метод comapre для сравнения элементов A1 [] в соответствии
// в порядке, определенном A2 [].

int compareByA2(const void* a, const void* b)

{

int idx1 = search(*(int*)a);

int idx2 = search(*(int*)b);

if (idx1 != -1 && idx2 != -1)

return idx1 - idx2;

else if (idx1 != -1)

return -1;

else if (idx2 != -1)

return 1;

else

return (*(int*)a - *(int*)b);

}

// Этот метод в основном использует qsort для сортировки A1 [] в соответствии с A2 []

void sortA1ByA2(int A1[], int size1)

{

qsort(A1, size1, sizeof(int), compareByA2);

}

// Программа драйвера для проверки вышеуказанной функции

int main(int argc, char* argv[])

{

int A1[] = { 2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8, 7, 5, 6, 9, 7, 5 };

// A2 [] = {2, 1, 8, 3, 4};

A2[0] = 2;

A2[1] = 1;

A2[2] = 8;

A2[3] = 3;

A2[4] = 4;

int size1 = sizeof(A1) / sizeof(A1[0]);

sortA1ByA2(A1, size1);

printf("Sorted Array is ");

int i;

for (i = 0; i < size1; i++)

printf("%d ", A1[i]);

return 0;

}

Выход :

Sorted Array is 2 2 1 1 8 8 3 5 5 5 6 6 7 7 7 9 9

Этот метод основан на комментариях читателей (Xinuo Chen, Pranay Doshi и javakurious) и составлен Анураг Сингхом.

Эта статья составлена Пиюшем . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Сортировать массив в соответствии с порядком, определенным другим массивом

0.00 (0%) 0 votes