Vik*_*ram 4 arrays algorithm search hashmap data-structures
我遇到了以下问题:
'找到数组中出现奇数次的所有元素'.
我对此的看法是:
使用HashMap:在数组中添加值作为HashMap中的键.对应于每个键的值将是遇到键的次数.
使用O(N log N)中的快速排序对数组进行排序,然后遍历数组以检查哪些元素出现奇数次.
您怎么看？有没有其他办法解决这个问题？如果不是,那么这两种方法中的哪一种更好？
提前致谢!
das*_*ght 15
您可以修改第一种方法来使用哈希集而不是哈希映射.
创建一个最初为空的哈希集.浏览数组的元素.对于每个元素,检查哈希集:如果当前数组元素不在集合中,则添加它; 否则,删除它.
当您到达数组的末尾时,您的哈希集将包含数组中出现的每个对象奇数次.
由于访问哈希集中的元素O(1),因此该算法具有O(N)时间复杂度.
"更好"取决于背景.使用散列映射或散列集会更快,并且具有不修改原始数组的优点,但它需要额外的O(N)内存.排序和计数需要更长时间并修改数组,但不需要额外的内存.
您选择哪种解决方案取决于您是否能够承受额外的内存.