匹配两个不同数组中的相同值

发布于 2025-01-11 07:22:49 字数 684 浏览 3 评论 0原文

想象一下，我们有 2 个具有完全相同元素（顺序不同）的数组，但作为限制，我们只能将数组 A 的元素与数组 B 的元素进行比较（这意味着我们不能对它们单独排序，然后打印出来结果）。目标是匹配 A 和 B 的元素并按升序排序。所以用这两个数组作为输入： A = [5, 8, 1, 2, 4, 3, 7, 6] 和 B = [1, 5, 2, 6, 8, 4, 7, 3]

输出应该像

A 1 2 3 4 5 6 7 8
B 1 2 3 4 5 6 7 8

我能想到的唯一解决方案现在的问题是，

    for (int i = 0; i < len; i++)
        for (int j = i; j < len; j++)
            if (A[i] == B[j])
                swap(A, i, j);

    for (int i = 0; i < len; i++)
        for (int j = i; j < len; j++)
            if (A[i] > B[j])
                swap(A, i, j);
                swap(B, i, j);

对于大输出来说，这将花费太长时间。这里有一个有效的算法可以使用吗？这使得它比 O(n^2) 更快

原文

Imagine we have 2 arrays that have the exact same elements (not in the same order) but, as a restriction, we can only compare elements of array A to elements of array B (meaning we can't sort them individually and then print out the result). And the goal is to match the elemnts of A and B and sort sort it in ascending order. So with these 2 arrays as input:
A = [5, 8, 1, 2, 4, 3, 7, 6] and B = [1, 5, 2, 6, 8, 4, 7, 3]

The output should be like

A 1 2 3 4 5 6 7 8
B 1 2 3 4 5 6 7 8

The only solution I can think of right now is

    for (int i = 0; i < len; i++)
        for (int j = i; j < len; j++)
            if (A[i] == B[j])
                swap(A, i, j);

    for (int i = 0; i < len; i++)
        for (int j = i; j < len; j++)
            if (A[i] > B[j])
                swap(A, i, j);
                swap(B, i, j);

That would take too long with big outputs though. Is there an efficient algorithm to use here? That makes it faster than O(n^2)

分享到QQ

分享到微博