将整数数组与其移位后的值进行比较

Question

我希望创建一个函数，比较两个数组，如果它们在某种顺序下具有相同的值（可能会被移动），则返回true。

例如：

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

相同，或者true

而

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

它们不相同，因此为false。

有什么想法吗？

- mardon

---

你想检查arr1和arr2的内容是否相同，而不考虑顺序吗？ - yano

@yano，编辑表示（暗示）它已经旋转，否则顺序相同。 - Weather Vane

请问您有什么问题？ - Weather Vane

你有写过任何代码或者至少尝试过吗？如果是，请发出来以便我们帮助您。 - Ahmed Aboumalek

哦，我明白了。我的第一反应是将arr1向右旋转一个位置，然后使用memcmp与arr2进行比较，反复执行此操作，直到找到匹配项或旋转arr1的长度。但我相信肯定有更优化的解决方案。首先，检查arr1和arr2是否具有相同的长度。 - yano

Answer 1

Here you are

#include <stdio.h>

int is_equivalent(const int a[], const int b[], size_t n)
{
    int success = 0;

    for ( size_t m = 0; !success && m < n;  )
    {
        // Try to find in the array a the first element of the array b
        // If there is no such an element then the arrays are different.
        // Otherwise compare elements of the arrays starting from the
        // found element in a and the first element in b
        while (m < n && a[m] != b[0]) ++m;

        if (m != n)
        {
            size_t i = 1;
            size_t j = ++m % n;

            while (i < n && b[i] == a[j])
            {
                ++i; ++j;
                j %= n;
            }

            success = i == n;
        }
    }

    return success;
}

int main( void )
{
    {
        int a[] = { 1, 2, 3, 4, 5 };
        int b[] = { 3, 4, 5, 1, 2 };

        printf("The arrays are equivalent: %d\n",
            is_equivalent(a, b, sizeof(a) / sizeof(*a)));
    }

    {
        int a[] = { 1, 2, 3, 4, 5 };
        int b[] = { 3, 4, 5, 2, 1 };

        printf("The arrays are equivalent: %d\n",
            is_equivalent(a, b, sizeof(a) / sizeof(*a)));
    }

    return 0;
}

程序输出为：

The arrays are equivalent: 1
The arrays are equivalent: 0

- Vlad from Moscow

---

@Paul 你说得对。但只需添加一个外部循环，该函数就可以适用于任何数组。 - Vlad from Moscow

@JohnKugelman 你需要找到第二个数组在第一个数组中的起始位置。为此，您需要在第一个数组中找到第二个数组的第一个元素，然后从找到的位置开始比较数组的所有元素。 - Vlad from Moscow

@VladfromMoscow 这段代码可以简化很多。您可以直接省略计算偏移量的循环，并且在不改变功能的情况下无需检查 m < n 就可以进行比较。这是一种蛮力法，但它能够工作。至于解释：我认为JohnKugelman的意思是您应该在问题中添加注释。个人而言，我没有理解代码的问题，但我怀疑OP不会那么容易理解。 - user4668606

Answer 2

尝试这个。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool check(size_t size, int arr1[], int arr2[]){
    int *temp = malloc(size * 2 * sizeof *temp);
    memcpy(temp, arr1, size * sizeof *temp);
    memcpy(temp+size, arr1, size * sizeof *temp);//[1,2,3] --> [1,2,3,1,2,3]

    size_t i;
    for(i = 0; i < size; ++i)
        if(memcmp(temp+i, arr2, size * sizeof *temp) == 0)
            break;
    free(temp);
    return i != size;
}    

#define TEST(size, a1, a2) puts(check(size, a1, a2) ? "same" : "not same")

int main(void) {
    int arr1[] = {1,2,3,4,5};
    int arr2[] = {3,4,5,1,2};
    int arr3[] = {3,4,5,2,1};
    int arr4[] = {1, 0, 1, 1, 0};
    int arr5[] = {1, 0, 1, 0, 1};
    size_t size = sizeof(arr1)/sizeof(*arr1);

    TEST(size, arr1, arr2);
    TEST(size, arr1, arr3);
    TEST(size, arr4, arr5);
}

- BLUEPIXY

---

尽管这段代码可能有助于解决问题，但它并没有解释为什么以及如何回答这个问题。提供这种额外的上下文将显著提高其长期价值。请编辑您的答案以添加说明，包括适用的限制和假设。仅仅因为问题不好和模糊，并不意味着答案应该简洁和无信息！ - Toby Speight

这几乎是不言自明的，所以没有必要添加进一步的解释。 - BLUEPIXY

@Paul 确定。我已经更改了算法。 - BLUEPIXY

@BLUEPIXY 看起来对我来说还不错。虽然这只是 OP 想要避免的暴力搜索... - user4668606

memcmp不是每次都要进行彻底搜索。 - BLUEPIXY

@BLUEPIXY，你认为memcmp是做什么的呢？实际上它在内部使用了一种优化过的穷举搜索方法。 - user4668606

Answer 3

如果这些数组只是彼此旋转得到的版本，那么它们必须具有相等的长度，并且必须存在至少一个偏移量，使得 rotate(arr1, offset) == arr2。

因此，我们知道 concat(arr2, arr2) 必须等同于 rotate(concat(arr1, arr1), offset)，因此必须包含未经旋转的 arr1 在位置 offset 上。

这就是经典的子字符串匹配问题。解决这个问题的算法不会比解决前面的问题更好，因为它们是等价的。

解决这个问题的一个相当简单的方法是消除可能的偏移量：

//generate a list of offsets from the first element in arr1
list offsets = indicesOf(arr1[0], arr2)

int i = 0
while !offsets.empty && i < length(arr1):
    //generate the rotational offsets of the next char
    list nextoffsets = indicesOf(arr1[i], arr2)
    //make offsets the list of offsets that are valid for all elements up to arr1[i]
    offsets = intersection(offsets, nextoffsets)

    i++

return !offsets.empty

- user4668606

---

我认为你缺少声明这些函数的头文件 - 它们在 <algorithm> 中吗？实际上，它们不可能在其中，因为这是 C，而不是 C++。 - Toby Speight

@TobySpeight 这显然是一道作业题。我愿意提供解决问题的方法和一些帮助理解问题的帮助，但不会提供更多。至于标题：这是伪代码，而不是实际的实现。 - user4668606

Answer 4

你可能对这个问题的C++等效版本感兴趣。看到标准库提供比C程序员可用的更高级别的抽象是很有启发性的。

首先，我们需要一个合理的函数签名。让我们将其设置为模板，这样我们就可以像使用std::vector和int一样愉快地使用std::array和struct Foo：

template<typename T>
bool equals_rotated(const std::vector<T>& a, const std::vector<T>& b);

还有一些简单的测试：

int main()
{
    const auto e = equals_rotated<int>;
    return !e({}, {})
        +   e({1, 2, 3, 4} , {1, 2, 3})
        +  !e({1, 2, 3}    , {1, 2, 3})
        +   e({1, 2, 3, 4} , {1, 2, 4, 3})
        +  !e({1, 2, 3, 4} , {4, 1, 2, 3})
        ;
}

实现很简单。我们知道，如果数组长度不同，则它们不能等价；反之，如果它们完全相同，则它们必须是等价的。因此，在这些情况下，让我们提前返回：

if (a.size() != b.size())
    return false;
if (a == b)
    return true;

对于一般情况，我们可以将a与自身连接起来，然后测试它是否包含b作为子序列。这会对内存需求产生影响，但它使实现变得简单：

auto v = a;
v.reserve(2*a.size());
std::copy(a.begin(), a.end(), std::back_inserter(v));
return std::search(v.begin(), v.end(), b.begin(), b.end()) != v.end();

---

如果我们把所有这些放在一起，包括必要的头文件，并添加一个包装器，以便我们可以从C中调用它，我们将得到：

#include <algorithm>
#include <iterator>
#include <vector>

template<typename IterA, typename IterB>
bool equals_rotated(IterA a_begin, IterA a_end, IterB b_begin, IterB b_end)
{
    // trivial tests
    if (a_end - a_begin != b_end - b_begin)
        return false;
    if (std::equal(a_begin, a_end, b_begin, b_end))
        return true;
    // Otherwise, make a copy of a+a
    std::vector<typename std::iterator_traits<IterA>::value_type> v;
    v.reserve(2 * (a_end - a_begin));
    const auto ins = std::back_inserter(v);
    std::copy(a_begin, a_end, ins);
    std::copy(a_begin, a_end, ins);
    // and test whether it contains b
    return std::search(v.begin(), v.end(), b_begin, b_end) != v.end();
}

template<typename T>
bool equals_rotated(const std::vector<T>& a, const std::vector<T>& b)
{
    return equals_rotated(a.begin(), a.end(), b.begin(), b.end());
}

extern "C" {
    bool is_rotated_array(int *a, size_t a_len, int *b, size_t b_len)
    {
        return equals_rotated(a, a+a_len, b, b+b_len);
    }
}

int main()
{
    const auto e = equals_rotated<int>;
    return !e({}, {})
        +   e({1, 2, 3, 4} , {1, 2, 3})
        +  !e({1, 2, 3}    , {1, 2, 3})
        +   e({1, 2, 3, 4} , {1, 2, 4, 3})
        +  !e({1, 2, 3, 4} , {4, 1, 2, 3})
        ;
}

- Toby Speight

Answer 5

#include <stdio.h>

int isArraySame(int arr1[], int arr2[], int len1, int len2){
    int var1=0;
    int var2=0;
    int index=0;

    for (index=0;index<len1;index++){
        var1+=arr1[index];
    }

    for (index=0;index<len2;index++){
        var2+=arr2[index];
    }

    if (var1==var2) return 1;
    return 0;
}

int main(){
    int arr1[] = {1,2,3,4,5};
    int arr2[] = {3,4,5,1,2};
    if (isArraySame(arr1, arr2, 5, 5)) {
        printf("true");
    } else {
        printf("false");
    }
    return 0;
}

- Adam

---

好的...不好意思。请考虑一下在 int arr1[] = {1,1,1}; int arr2[] = {3}; 或者 int arr1[] = {-1,2,1}; int arr2[] = {1,1,0}; 的情况下，你的函数会返回什么。 - Bob__