根據另一個數組定義的順序對一個數組進行排序  


難度級別 容易獎學金
經常問 亞馬遜 Microsoft微軟 SAP實驗室 Snapchat 雅虎 百會
排列 搜索 排序

問題陳述  

給你兩個 數組 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方法是用作快速排序算法的預定義方法。 它是對任何列表進行排序的最快算法之一。 在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) 哪裡 “m”個 是arr1的長度& “ n” 是arr2的長度。 由於我們使用了qsort(排序算法)。 我們已經實現了 O(n log n) 因素。 在這裡,搜索是使用線性搜索完成的。 而不是這樣做,我們可以輕鬆地使用HashMap,這將進一步降低時間複雜度。

也可以看看
前K個常見元素

空間複雜度

O(log n), 哪裡 “m”個“ n” 是Arr1和Arr2的長度。 因為我們已經使用快速排序完成了排序,所以空間複雜度就是因為這個原因。 但是整個程序需要 O(N + M)。