加扰数组 – 检查数组中的元素是否与O（n）复杂度匹配（顺序无关紧要）

我正在尝试编写带有两个数组的代码，如果元素匹配（顺序无关紧要）则返回1，如果它们不匹配则返回0。

1. 必须是O（n）

我写了几个不同的算法，一个比较两个数组的总和，如果它们是相同的则返回1，如果它们不是，则为0，但如果数组包含总结为相同的数据的不同值元素，那么这不是工作。

找到一个O（n ^ 2）很简单（两个循环，比较，然后迭代A等的下一个位置..

我似乎无法找出这样做的O（n）。 我当前的代码取值的差异，如果它的0返回1仍然不知道如何处理不排序相同的乱序数组。 是否有O（n）这样做？

int scrambled( unsigned int a[], unsigned int b[], unsigned int len) { int count[100]; int flag = 1; int i; for(i=0; i<100; i++){ count[i] = 0; } for(i=0; i<len; i++){ count[a[i]]++; count[b[i]]--; } for(i=0; i<100; i++){ if(count[i] != 0){ return 0; } } return flag; 

Answer 1

如果你可以使用C ++ 11，可以在O(n)时间内填充std::unordered_set然后你可以执行O(n)元素成员资格测试（即使你做了两次它仍然是O(n) ;常数乘数不要算）。

如果C ++ 11已经用完，你仍然可以使用与手写哈希集相同的基本算法，或者如果每个元素都在有界范围内，你可以使用计数排序 （即O(n+k)由于专注于数字范围，如果范围很小， k分量并不重要）。