难度: Easy
Submission
运行时间: 27 ms
内存: 16.2 MB
from typing import List
class Solution:
def largestUniqueNumber(self, nums: List[int]) -> int:
freq = {}
max_unique = -1
# 统计每个数字的出现频率
for num in nums:
if num in freq:
freq[num] += 1
else:
freq[num] = 1
# 遍历字典，找到仅出现一次的最大整数
for num, count in freq.items():
if count == 1 and num > max_unique:
max_unique = num
return max_unique
solution = Solution()
nums = [5, 7, 3, 9, 4, 9, 8, 3, 1]
result = solution.largestUniqueNumber(nums)
print(result) # 输出：8
Explain
这个题解的思路如下： 1. 首先，使用一个字典 `freq` 来统计数组中每个数字出现的频率。遍历数组 `nums`，对于每个数字，如果它已经在字典中，则将其对应的频率加 1；否则，将其频率初始化为 1。 2. 接下来，遍历字典 `freq`，找到仅出现一次且值最大的数字。初始化一个变量 `max_unique` 为 -1，表示当前找到的最大唯一数。对于字典中的每个键值对，如果该数字的频率为 1 且大于当前的 `max_unique`，则更新 `max_unique` 为该数字。 3. 最后，返回 `max_unique` 作为结果，即为仅出现一次的最大整数。如果不存在这样的数，则返回初始值 -1。
时间复杂度: O(n)
空间复杂度: O(n)
from typing import List
class Solution:
def largestUniqueNumber(self, nums: List[int]) -> int:
freq = {} # 用于存储每个数字的出现频率
max_unique = -1 # 初始化最大唯一数为 -1
# 统计每个数字的出现频率
for num in nums:
if num in freq:
freq[num] += 1
else:
freq[num] = 1
# 遍历字典，找到仅出现一次的最大整数
for num, count in freq.items():
if count == 1 and num > max_unique:
max_unique = num
return max_unique # 返回仅出现一次的最大整数，如果不存在则返回 -1
solution = Solution()
nums = [5, 7, 3, 9, 4, 9, 8, 3, 1]
result = solution.largestUniqueNumber(nums)
print(result) # 输出：8
Explore
在统计频率时，使用字典来存储每个数字的频率。如果数组非常大，内存占用主要取决于数组中不同数字的数量。在最坏的情况下，即数组中每个元素都不相同，字典将需要存储与数组长度相等的条目数，这将显著增加内存使用。对于非常大的数组，这可能导致内存不足的问题，尤其是在内存资源有限的环境中。改善内存使用的一种方式可能是使用更内存效率高的数据结构，如计数排序或位图，尤其是当元素的范围已知且有限时。
算法已经考虑了所有数字都重复出现的情况。在算法中，如果所有数字都至少重复一次，那么字典遍历时不会找到任何频率为1的数字，因此变量 `max_unique` 将保持其初始化的值 -1。这意味着函数将正确返回 -1，表示数组中没有唯一数字。这符合题目要求的正确处理方式。
在遍历字典 `freq` 时，算法检查每个条目的频率是否为1（表示数字唯一），并与当前存储的最大唯一数 `max_unique` 比较。如果找到的唯一数字大于 `max_unique`，则更新 `max_unique` 的值。这保证了在遍历结束时，`max_unique` 存储的是所有唯一数字中的最大值。因此，通过这种方式，算法确保最终找到并返回的是最大的唯一数。
当前的实现已经可以正确处理空数组的情况。当输入数组 `nums` 为空时，字典 `freq` 也将为空，因此在遍历字典时不会有任何操作执行。变量 `max_unique` 将保持其初始值 -1，然后被返回。因此，该方法已正确处理空数组输入的情况，无需进行修改。