Рубрики

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

Учитывая два массива 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