java在整数数组中查找第一个非重复数

Question

我有一道考试题：

Given an integer array find the first number which is not repeating in array using O(N) time complexity and O(1) space complexity.

我想不出任何解决办法。我知道我可以迭代数组并维护一个linkedhashmap，它将存储数组元素和它出现的次数，最后我必须搜索hashmap来找到那个数字。空间复杂度大于O（1），但我想不出其他解决方案

我也仔细阅读了这个问题，并说阵列的最大大小将是100万。我认为，如果我们可以创建一个自定义hashmap，该hashmap将使用100万大小的固定大小数组，那么这可以在O（1）空间复杂度中实现，因为在这种情况下，所需的存储是恒定的，但如果我是正确的，则无法确定。如果还有其他解决方案，请告诉我

Answer 1

在给定整数数组中查找第一个非重复数

更新：找到了更好的解决方案。 我认为我们可以使用附加的数据结构（如HashMap）在O(n)时间复杂度内解决它。遍历数组，将元素作为键，将数组中元素的索引位置作为映射中的值。如果密钥已经存在，则可以删除密钥-值对，或者只将值设置为-1。 遍历整个数组后，我们可以从hashmap中获取keySet（），然后找到值最低的键（忽略-1）。 所以这就是 时间复杂度：O（N） 空间复杂度：O（N）

旧解决方案：我们可以通过创建另一个数组来解决这个问题，该数组是通过对给定数组进行排序得到的。这需要O(nlogn)时间。 然后我们可以遍历给定输入数组中的每个元素，尝试查找元素&；与排序数组中的下一个元素比较，如果对给定数组中的下一个元素重复continue，如果不重复，则在给定整数输入数组中找到第一个非重复元素

时间复杂度：O（nlogn）
空间复杂度：O（n）

注：很抱歉，我没有阅读所有的评论，詹姆斯·坎泽已经在评论中提供了这个解决方案，感谢他

Answer 2

我认为解决问题的诀窍是：

max size of array would be 1million

自：

O(1) space means that the memory required by the algorithm is constant

然后，给定常数1M，空间复杂度将自动变为O（1）。笔记1M仍然是一个常量，尽管它确实是一个很大的数字。因此，我们只需要关注时间复杂性

使用LinkedHashMap我们可以用O(1)添加新元素，用O(1)检索元素，因此更新条目也需要O（1）。它也preserves the order。因此，我们可以找到最早的条目

然后，问题将通过两个步骤变得简单：

1. 建立LinkedHashMap-->；O（n）
2. 查找其计数为0的最早数字-->；O（n）

上述每个步骤都需要O（n），因此总体time complexity是O(2n) = O(n)

Answer 3

我是用PowerShell做的

[int[]]$arr = @(6,2,1,2,6,1,7)

$Collection = New-Object 'System.Collections.Generic.list[System.Object]'
$props=[ordered]@{"Index"=9999;"Value"=9999;"Numcount"=9999}
$record = New-Object -TypeName psobject -Property $props
$Collection.Add($record) #This record is added to do a Contains operation 
#for future items to be added in the $collection object

for($i =0;$i -lt $arr.Length;$i++)
{
if($i -eq 0)
{
    $props=[ordered]@{"Index"=$i;"Value"=$arr[$i];"Numcount"=1}
    $record = New-Object -TypeName psobject -Property $props
    $Collection.Add($record)
}


elseif($Collection.value.Contains($arr[$i]))
{

    $count = ($Collection | ?{$_.Value -eq $arr[$i]} | select -First `
1).Numcount
    ($Collection | ?{$_.Value -eq $arr[$i]} | select -First 1).Numcount = `
$count+1
}
else
{
    $props=[ordered]@{"Index"=$i;"Value"=$arr[$i];"Numcount"= 1}
    $record = New-Object -TypeName psobject -Property $props
    $Collection.Add($record)
}

}
Write-Output "The first non repeating number in the array is listed below"
$Collection | Sort-Object Numcount -Descending | ?{$_.Numcount -eq 1} | 
Select -First 1

OUTPUT:-
The first non repeating number in the array is listed below
Index Value Numcount
----- ----- --------
6     7        1

Answer 4

如果除一个元素外的所有元素都有两个（或2的倍数）条目，这将是非重复的，则可以使用XOR运算符

例如：

int x=arr[0];
for(i=1;i<1000;i++)
  x^=a[i];
printf("Non-repeating: %d",x);

与自身异或的任何数字都是0。因此，如果任何数字出现两次，那么在整个XOR结果中它将是0，从而在x中只留下非重复数字

注意：如果您有一百万个数字，那么存储XOR结果的变量必须足够大