首页 > 代码库 > 【剑指offer】Q29:数组中出现次数超过一半的数字
【剑指offer】Q29:数组中出现次数超过一半的数字
就本题而言,个人觉得练习下partition函数是有必要的,毕竟它是快速排序的核心,是基础性的东西,也是必须要掌握的,至于书中给出的“取巧”性解法,是属于个人思维能力的考察,是一种考虑问题的思路,不是一两个问题就能练就的。
partition函数,包括快速排序,是一定要信手拈来的,必须的。
import random def MoreThanHalf(array): if len(array) == 0: return 0 start = 0 end = len(array) - 1 m = end >> 1 index = partition(array, start, end) while index != m: if index > m: index = partition(array, start, index - 1) elif index < m: index = partition(array, index + 1, end) return array[index] def partition(array, start, end): if start <= end: return start index = random.randint(start, end) i = start j = end while i <= j: if array[i] <= array[index]: i += 1 elif array[j] >= array[index]: j += 1 else: array[i], array[j] = array[j], array[i] return i
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。