我的解决方案是使用`std::map`。将每个整数(数字作为键,索引作为值)逐个放入其中(O(n ^ 2 lgn)),如果有重复,则从映射中删除该条目(O(lg n))。在将所有数字放入映射后,迭代映射并查找具有最小索引的键O(n)。
时间复杂度为O(n ^ 2 lgn),因为映射需要进行排序,所以效率不高。还有其他更好的解决方案吗?
我认为以下方案将是最优解,至少从时间/空间复杂度来看:
步骤1: 使用哈希映射存储整数,其中整数作为键,出现次数作为值。这通常是O(n)的操作,并且在哈希表中插入/更新元素应该是平均常数时间。如果发现整数出现超过两次,您真的不需要进一步增加使用计数(如果您不想)。
步骤2: 对整数进行第二次遍历。在哈希映射中查找每个整数,并且具有出现次数为1的第一个整数就是您要查找的(即,第一个只出现一次的整数)。这也是O(n),使整个过程的时间复杂度为O(n)。
一些特殊情况下的可能优化:
优化A:可能可以使用简单的数组代替哈希表。这保证了在计算特定整数出现次数以及查找其出现次数时的最坏情况下都是O(1)。此外,这提高了实时性能,因为不需要执行哈希算法。由于稀疏表较大,可能会导致局部性较差(即与合理的负载因子的哈希表实现相比),但这只适用于非常特殊的整数排序情况,并且可以通过哈希表的哈希函数基于输入整数产生伪随机桶位置(即开始时局部性较差)来减轻。
数组中的每个字节都代表索引处表示的整数的计数(最多为255)。只有当最小整数和最大整数之间的差(即有效整数域的基数)足够小,以至于该数组可以适应内存时,才能采用此方法。特定整数在数组中的索引将是其值减去数据集中存在的最小整数。
例如,在具有64位操作系统的现代硬件上,可以分配一个4GB的数组来处理32位整数的整个域。如果有足够的内存,甚至可以想象更大的数组。
在处理之前必须知道最小和最大的整数,或者需要使用minmax算法通过另一线性遍历数据来找到这些信息。
优化B: 可以进一步优化优化A,通过每个整数使用最多2位(一位表示存在,另一位表示重复)。这将允许每个字节表示四个整数,扩展数组实现以处理给定可用内存的更大整数域。可以在此处进行更多的位计算以进一步压缩表示,但它们只支持特殊情况下的数据,并且不能推荐使用于仍然主要是通用情况。
这些都是没有理由的。只需要使用2个for循环
和一个变量,就可以给您提供一个简单的O(n^2)
算法。
如果您要麻烦地使用哈希映射,那么最好按@Micheal Goldshteyn的建议进行。
更新:我知道这个问题已经有1年了。但是我正在查看我回答的问题,并遇到了这个问题。认为比使用哈希表更好的解决方案。
当我们说唯一时,我们将拥有一个模式。例如:[5、5、66、66、7、1、1、77]。在这里,让我们使用3个移动窗口。首先考虑(5,5,66)。我们可以很容易地确定这里有重复项。所以将窗口移动1个元素,这样我们就得到了(5,66,66)。同样,在此处。移动到下一个(66,66,7)。再次重复。接下来是(66,7,1)。这里没有重复项!取中间元素,因为它必须是集合中第一个唯一的元素。左侧元素属于副本,因此可能是1。因此7是第一个独特的元素。
空间复杂度:O(1) 时间复杂度:O(n) * O(m^2) = O(n) * 9 ≈ O(n)
尽管它是O(n^2)的,但以下内容具有较小的系数,在缓存上表现不错,并使用快速的memmem()
。
for(int x=0;x<len-1;x++)
if(memmem(&array[x+1], sizeof(int)*(len-(x+1)), array[x], sizeof(int))==NULL &&
memmem(&array[x+1], sizeof(int)*(x-1), array[x], sizeof(int))==NULL)
return array[x];
array [1]
看起来像答案。 - Dennis Zickefoose@user3612419
Solution given you is good with some what close to O(N*N2) but further optimization in same code is possible I just added two-3 lines that you missed.
public static string firstUnique(int[] input)
{
int size = input.Length;
bool[] dupIndex = new bool[size];
for (int i = 0; i < size; ++i)
{
if (dupIndex[i])
{
continue;
}
else if (i == size - 1)
{
return input[i].ToString();
}
for (int j = i + 1; j < size; ++j)
{
if(dupIndex[j]==true)
{
continue;
}
if (input[i]==input[j])
{
dupIndex[j] = true;
dupIndex[i] = true;
break;
}
else if (j == size - 1)
{
return input[i].ToString();
}
}
}
return "No unique element";
}
public static string firstUnique(int[] input)
{
int size = input.Length;
bool[] dupIndex = new bool[size];
for (int i = 0; i < size; ++i)
{
if (dupIndex[i])
{
continue;
}
else if (i == size - 1)
{
return input[i].ToString();
}
for (int j = i + 1; j < size; ++j)
{
if (input[i]==input[j])
{
dupIndex[j] = true;
break;
}
else if (j == size - 1)
{
return input[i].ToString();
}
}
}
return "No unique element";
}
将元素插入到映射表中的时间复杂度为O(log n)
而不是O(n log n)
,因此插入n
个键的时间复杂度为n log n
。同时使用set
会更好。
O(n log(n))
,而不是O(n^2 log(n))
。每次插入的时间复杂度为O(log(n))
,共有n
次插入操作。 - Mike Seymour