检查两个数组是相似的 [英] Check if two arrays are similar

问题描述

由于两个数组，检查他们是否是相似的（即具有相同的整数，每个整数出现的次数相同）。

Given two arrays, check if they're similar (i.e. have the same integers and each integer occurs same number of times).

例如：

int arr1[5] = { 3, 5, 2, 5, 2}
int arr2[5] = { 2, 3, 5, 5, 2}

我是不允许使用排序和哈希表。它应该是为O（n），并应不使用任何额外的空间。

I was not allowed to use sorting and hashtable. It should be O(n) and should not use any extra space.

这是一个面试问题。

试着用类似的规则：

1. 整数两个数组总和应该是相同
2. 在两个数组整数的产品应该是一样的。
3. 所有整数XOR应该是零

但还是面试官并不开心。也许我错过了一些角落的情况。

But still interviewer is not happy. Maybe I'm missing some corner cases.

推荐答案

我能想到的一种方式来执行此任务，如果元素的值是整数，由 N （ 1，...，N ），其中 N 是数组的大小（适用于您的例子）

I can think of one way to perform this task, if the elements values are integers and bounded by n (1...n), where n is the size of the arrays (this applies to you example):

在每个数组，每个元素 X ，我们改编[X％（N + 1）-1] + = N + 1 。我们使用MOD，​​因为该元素可以通过工艺各不相同，通过使用MOD我们得到的出现在原始数组中的元素。

In each array, for each element x, we do arr[x%(n+1)-1] += n+1. we use mod since the element may vary through the process, by using mod we get the element that appeared in the original array.

我们做的是通过将计算值 v 的出现在改编[V] 数 N + 1 ，那么我们可以得到这样做的原始值改编[V]％（N + 1）作为值由 N 界，和外观的做改编数[V] /（N + 1）。

What we do is count the number of appearances of a value v in arr[v] by adding n+1, then we can get the original value by doing arr[v]%(n+1) as the value is bounded by n, and the number of appearances by doing arr[v]/(n+1).

在最后，我们每个值出现的次数比较 A 和 B ，如果为任意值它们是不同的，我们返回假。如果计数是相同的所有值，我们返回真。

In the end we compare the number of appearances of each value in A and B, if for any value they are different, we return false. if the counting was the same for all the values, we return true.

这是一个 O（N）时间的解决方案，需要 O（1）内存。

This is an O(n) time solution that requires O(1) memory.

下面的算法：

bool checkIfArraysAreSimilar(int[] A, int[] B)
{
    n = A.length; // = B.length
    int i;

    for (i = 0; i < n; i++)
    {
        A[(A[i]%(n+1))-1] += n+1;
        B[(B[i]%(n+1))-1] += n+1;
    }

    for (i = 0; i < n; i++)
    {
        if (A[i] / n+1 != B[i] / n+1)
            return false;
    }

    return true;
}

这篇关于检查两个数组是相似的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！