数组里一个数字出现超过一半,找出这个数

这是一个很经典的面试题了,不过要想一下就想到最佳解题方案还是有一定的难度的~

基本上有以下几种解决方法:

  1. 排序,然后取n/2即为那个数,即使使用效率比较高的快速排序,其时间复杂度仍为O(nlogn)+1
  2. hashmap,遍历一次数组填充hashmap,然后遍历一次hashmap找到这个数,时间复杂度为O(n),空间复杂度为O(n)
  3. 这个方法比较难想到-每次找到两个不同的数,然后从数组中删除,最后找不到两个相同的数时就是就是这个数。使用这个方法一定要注意前提:这个数在数组中的数量要超过一半,否则不能使用这个方法。时间复杂度O(n)

未经允许不得转载:开心猿社区 » 数组里一个数字出现超过一半,找出这个数

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址