【算法岗面试-算法题】LeetCode 169 多数元素 python

题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

思路一：排序取中间

如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为n/2的元素（下标从 0 开始）一定是众数。

Class Solution：
    def majorityRlement(self,nums:List[int]):
        nums.sort()
        return nums[len(nums)//2]

时间复杂度为O(nlogn）

如果面试的时候答这个方法，可能会从两个角度继续问：

（1）排序用什么方法比较快？（快排or堆排）具体写一下（写法见文末）

（2）除了这个方法，有没有更快的方法？摩尔投票法

思路二：摩尔投票法

摩尔投票法是一种使用线性时间和常数空间查找大部分元素序列的算法。

思路：

       如果我们把众数记为+1，把其他数记为-1，将它们全部加起来，显然和大于0，从结果本身，我们可以看出众数比其他数多。

算法：

        本质上，摩尔投票算法就是找nums的一个后缀suf，suf[0]就是后缀中的众数。我们维护一个计数器，如果遇到一个我们目前的候选众数，就将计数器+1，否则-1。只要计数器等于0，就将nums中之前访问的数字全部忘记，并把下一个数字当做候选的众数。

举例：

【1，1，2，1，2，3|2，1|2，2，1，1|1，1，1，1】

竖线为每次计数器归零的情况。首先下标为0的1为候选众数，在下标为5处，计数器变为0；下标为6的2再次成为候选众数，以此类推。最后总有一个后缀满足计数器是大于0的，此时这个后缀的众数就是整个数组的众数。

class Solution:
    def majorityElement(self,nums):
        count = 0
        candidate = None
        for num in nums:
            if count==0:
                candidate = num
            if num==candidate:
                count+=1
            else:
                count-=1
        return candidate

 

p.s.  排序算法

1 快排

快排的时间复杂度为O(nlogn）

快排的思想：经典分治算法

步骤：1.从数列中挑出一个元素作为基准值

           2.分区过程，将比基准值大的放到右边，小于或等于它的数都放到左边

           3.再对左右区间递归执行第二步，直到各区间只有一个数

快排的性能和划分子数组的长度密切相关，直观地理解如果每次规模为n的问题，我们都划分成1和n-1，每次递归的时候又向n-1集合中递归，这种情况是最坏的，时间代价为O(n^2),我们可以引入随机化来加速这个过程，这个时间代价的期望为O(n)。

import random
class Solution：
    def quickSelect(self,a,l,r):
        q = self.randomPartition(a,l,r)
        self.quickSelect(a,q+1,r)
        self.quickSelect(a,l,q-1)


    def randomPartition(self,a,l,r):
        i = random.randint(l,r)
        a[i],a[r] = a[r],a[i]
        return self.partition(a,l,r)
    
    def partition(self,a,l,r):
        x = a[r]
        i = l-1
        for j in range(l,r):
            if a[j]<x:
                i+=1
                a[i],a[j] = a[j],a[i]
        i+=1
        a[i],a[r] = a[r],a[i]
        return i
    
    def sortmain(self,nums):
        self.quickSelect(nums,0,len(nums)-1

2 堆排序

重要过程：「建堆」、「调整」和「删除」

步骤：构建大根堆：存入二叉树，先按照顺序将该组元素构建成一棵完全二叉树；调整元素：从第一个非叶子节点为根节点的子树开始，调整为大根堆；调整倒数第二个非叶子节点的子树...调整完毕。

class Solution:
    def maxHeapify(self,a,i,heapSize):
        l = i*2+1
        r = i*2+2
        largest = i
        if l<heapSize and a[l]>a[largest]:
            largest = l
        if r<heapSize and a[r]>a[largest]:
            largest = r
        if largest != i:
            a[i],a[largest] = a[largest],a[i]
            self.maxHeapify(a,largest,heapSize)

    def buildMaxHeap(self,a,heapSize):
        for i in range(heapSize//2,-1,-1):
            self.maxHeapify(a,i,heapSize)

    def sortmain(self,nums):
        heapSize = len(nums)
        self.buildMaxHeap(nums,heapSize)
        for i in range(len(nums)-1,-1,-1):
            nums[0],nums[i] = nums[i],nums[0]
            heapSize -= 1
            self.maxHeapify(nums,0,heapSize)