根据另一个数组定义的顺序对一个数组进行排序


难度级别 易得奖学金
经常问 亚马逊 微软 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,这将进一步降低时间复杂度。

空间复杂度

O(log n), 哪里 “m”个“ n” 是Arr1和Arr2的长度。 因为我们已经使用快速排序完成了排序,所以空间复杂度就是因为这个原因。 但是整个程序需要 O(N + M)。