我在考试中遇到了这个问题：
给定一个整数数组，使用O(N)时间复杂度和O(1)空间复杂度找到第一个不重复的数字。
我想不出任何解决方案。我知道可以遍历整个数组并维护一个linkedhashmap，它将存储数组元素和它出现的次数，然后最后要在hashmap中搜索以找到那个数字。空间复杂度大于O（1），但我想不出其他解决方案。
我还仔细阅读了问题，并说数组的最大大小将为100万。我认为，如果我们可以创建一个自定义哈希映射，它将利用一个固定大小的1百万大小的数组，那么可以在O（1）空间复杂度下完成此操作，因为在这种情况下所需的存储量将是恒定的，但不确定我是否正确。请告诉我是否有其他解决方案。
int x=arr[0];
for(i=1;i<1000;i++)
x^=a[i];
printf("Non-repeating: %d",x);
x中。我使用 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
我认为解决这个问题的诀窍是：
数组的最大大小将会是一百万
因为：
O(1)空间意味着算法所需的内存是恒定的
因此，给定常数1M，空间复杂度将自动变为O(1)。注意：即使它是一个非常大的数字，1M仍然是一个常数。因此，我们只需要关注时间复杂度。
使用LinkedHashMap，我们可以添加一个新元素并检索具有O(1)的元素，因此更新条目也将花费O(1)。它还保留顺序。因此，我们可以找到最早的条目
然后问题就变得简单了，分为两步：
上述每个步骤都需要O(n)，因此总体时间复杂度为O(2n) = O(n)。