我想首先返回数组中的非重复元素(第一次相遇,从左到右)。
我有一个算法可以很容易地返回数组中不重复的最小整数,只使用数组作为额外空间,长度是数组中的最大整数值:
// smallest non repeating integer
int firstNonRepeatingInteger(int* input, int n)
{
max = std::numeric_limits<int>::min() ;
for(int i = 0 ; i < n ; i++)
{
if(input[i] > max)
max = input[i];
}
int* count = new int[max];
for(int i = 0 ; i < n ; i++)
count[input[i]] += 1 ;
int j = 0;
while(count[i] != 1)
j++ ;
if(j < n)
return input[count[j]] ;
else
return -1 ;
}
但是,除了使用另一个 n 数组存储遇到整数的时间之外,我找不到找到第一个相遇的算法。
有什么想法吗?第一个算法的任何其他实现?
谢谢
最佳答案
你几乎成功了:
#include <limits>
#include <iostream>
int firstNonRepeatingInteger(int* input, int n)
{
int min = std::numeric_limits<int>::max() ;
int max = std::numeric_limits<int>::min() ;
// Find min/max values in input array.
for(int i = 0; i < n; ++i)
{
if (input[i] > max)
max = input[i];
if (input[i] < min)
min = input[i];
}
int* count;
if (max - min + 1 > n)
{
count = new int[max - min + 1];
// count has more elements than input, so only initialize
// those elements which will be used.
for(int i = 0; i < n; ++i)
count[input[i] - min] = 0;
}
else
{
// Just initialize everything which is more efficient if
// count has less elements than input.
count = new int[max - min + 1]();
}
// Count number of occurrences.
for(int i = 0; i < n; ++i)
++count[input[i] - min];
// Find first non repeating element and return its index,
// or -1 if there is none.
int index = -1;
for (int i = 0; i < n; ++i)
{
if (count[input[i] - min] == 1)
{
index = i;
break;
}
}
delete[] count;
return index;
}
int main()
{
int values[5] = {-2, 4, 6, 4, -2};
int index = firstNonRepeatingInteger(values, 5);
if (index >= 0)
{
std::cout << "Found first non repeating integer " << values[index] <<
" at index " << index << "." << std::endl;
}
else
std::cout << "Found no non repeating integer in array." << std::endl;
return 0;
}
请注意您的代码有几个问题:
- 您从未删除分配的内存。
new int[max]
不会用零初始化数组。您需要改用new int[max]()
。请注意将所有元素设置为零的空括号(参见 ISO C++03 5.3.4[expr.new]/15)。- 输入数组中的负值将导致内存访问冲突。
关于C++ 在具有 O(n) 空间的数组中找到第一个非重复整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12771582/