面试常考算法题01

距离上次更新博客又有一个月了，最近这一个月还是在忙着找实习与秋招提前批。从2月底到6月中旬，差不多折腾了4个月，这中间经历了不少心酸，今年的算法(尤其是CV)真的是神仙打架。最后所幸还可以，拿到了两个机器学习的实习offer，分别是滴滴出行的数据算法实习生和哈啰出行的机器学习算法实习生。下面这几篇博文我将总结面试中常考的算法题，今天是第一篇！

---

无序数组中的第k大的元素

在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第 k个最大的元素，而不是第k个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

---

解题思路

类似快排的划分思路

先任取一个数，把比它大的数移动到它的左边，比它小的数移动到它的右边。移动完成一轮后，看该数的下标(从0计数)，如果刚好为k-1则它就是第k大的数，如果小于k-1，说明第k大的数在它右边，如果大于k-1则说明第k大的数在它左边，取左边或者右边继续进行移动，直到找到。

---

Python代码

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """    
        start = 0
        end = len(nums) - 1

        while start <= end:
            index = self.partition(nums, start, end)
            if index == k - 1:
                return nums[index]
            elif index > k - 1:
                end = index - 1
            else:
                start = index + 1

        return -1


    def partition(self, nums, low, high):
        """
        基于快排的划分算法
        """   
        pivot = nums[low]

        while low < high:
            while low < high and nums[high] <= pivot:
                high -= 1
            nums[low] = nums[high]
            while low < high and nums[low] > pivot:
                low += 1
            nums[high] = nums[low]

        nums[low] = pivot
        return low