如何查网站是那家做的/中国十大新闻网站排名

最近遇到的几个小问题，记录一下~~~
1、【快排和堆排序实现寻找第K大数】
快排和堆排序实现寻找第K大数github地址
2、【两个二维数组相乘】

3、【wmd讲解】

4、【三个激活函数的优缺点】

5、【LSTM解决的问题以及解决方法】

6、【fasttext原理】

7、【字典树的原理】

8、【过拟合 欠拟合了怎么办】

9、【正则项的作用】

1、求第K大数

leetcode # 215

【解法1 快排+分治算法】

利用快速排序算法找到pivotIndex（前后的分界点，左边的全都大于pivotIndex，右边的全都小于pivotIndex），判断当前pivot与K的大小关系

if pivotIndex == k: return nums[pivotIndex]if pivotIndex > K : 只需要对数组前pivotIndex-1个进行递归找第K大数if pivotIndex < K: 只需要对数组中pivotIndex+1后的进行递归

主要是利用一个Partition函数，得到分界点。这里提供两种写法的Partition函数。我觉得第一种比较好理解啦~~~

这里是从大到小进行排序，左边的全部大于pivotINDEX,右边的全部小于。

【Partition函数 第一种写法】

 def partition(self, nums, begin, end):left = begin +1right = endwhile left <= right:if nums[left] < nums[begin] and nums[right] > nums[begin]:nums[left],nums[right] = nums[right],nums[left]if nums[left] >= nums[begin]: left += 1if nums[right] <= nums[begin]: right -= 1nums[begin], nums[right] = nums[right],nums[begin]return right

【Partition函数 第二种写法】

 def Partition(self, nums, left, right):pivot = leftindex = pivot+1i = indexwhile i <= right:if nums[i] > nums[pivot]:nums[i], nums[index] = nums[index], nums[i]index += 1i += 1nums[pivot], nums[index-1] = nums[index-1], nums[pivot]return index - 1

【找第K大数】

就是利用上述Partition函数找到分界点的index，然后判断跟K的大小。
也是有两种，一种传入left和right，一种不传入。

def findKthLargest(self, nums, k):pivot = nums[0]left = 0right = len(nums)-1while True:pos = self.partition(nums, left, right)if pos == k-1:return nums[pos]if pos < k-1:left = pos+ 1else: right = pos- 1

# 这个函数有个bug，return的值为空，但是能够print出来，不知道什么原因。def findKthLargest(self, nums, k, left = None, right = None):left = 0 if not isinstance(left, (int,float)) else leftright  = len(nums)-1 if not isinstance(right, (int, float)) else right
#         print(left, right)index = self.Partition(nums, left, right)val = k-1if index == val :return nums[index]if index < val :self.findKthLargest(nums, k, index+1,right)else:self.findKthLargest(nums, k, left, index-1)

【解法二 利用堆排序】

堆排序时间复杂度的讲解

根据上述讲解，结论就是
哪个算法更加好？

Max: Time: O(n + klog(n)) | Space: O(n)
Min: Time: O(k) + O((n-k) * logk) | Space: O(K)

如果考虑k无限接近n
Max: O(n + nlog(n)) ~= O(nlogn)
Min: O(n + logk) ~= O(n)

如果考虑k = 0.5n
Max: O(n + nlogn)
Min: O(n + nlogn)

如果考虑n 无限大
Max: O(constant * n) 为什么是constant * n，参考
Min: O(log(k) * n)

都是利用shiftdown进行建堆

【最大堆寻找第k大数】

class FindKthLargestNum_maxHeap():def buildHeap(self,nums):if nums == []:return Nonesize = len(nums)for i in range(size//2-1, -1,-1):self.shiftdown(nums, i, size)return numsdef shiftdown(self, nums, i, size):left = 2*i +1right = 2*i +2maxIndex = iif left < size and nums[left] > nums[maxIndex]:maxIndex = leftif right < size and nums[right] > nums[maxIndex]:maxIndex = rightif maxIndex != i:nums[maxIndex], nums[i] = nums[i], nums[maxIndex]self.shiftdown(nums, maxIndex,size)return numsdef findKthLargestNum(self,nums, k):self.buildHeap(nums)for i in range(len(nums)-1, len(nums)-k, -1):nums[i] , nums[0] = nums[0], nums[i]self.shiftdown(nums, 0, i)return nums[0]
if __name__ == '__main__':a = [21,42,59,83,20,25,16]k = 3res = FindKthLargestNum_maxHeap().findKthLargestNum(a, k)print('kth largest num is',res)

【用最小堆找第K大数】

class FindKthLargestNum_maxHeap():def buildHeap(self,nums):if nums == []:return Nonesize = len(nums)for i in range(size//2-1, -1,-1):self.shiftdown(nums, i, size)return numsdef shiftdown(self, nums, i, size):left = 2*i +1right = 2*i +2minIndex = iif left < size and nums[left] < nums[minIndex]:minIndex = leftif right < size and nums[right] < nums[minIndex]:minIndex = rightif minIndex != i:nums[minIndex], nums[i] = nums[i], nums[minIndex]self.shiftdown(nums, minIndex,size)return numsdef findKthLargestNum(self,nums, k):self.buildHeap(nums)for i in range(len(nums)-1, k-1, -1):print(i,nums)nums[i] , nums[0] = nums[0], nums[i]self.shiftdown(nums, 0, i)return nums[0]
if __name__ == '__main__':a = [21,42,59,83,20,25,16]k = 4res = FindKthLargestNum_maxHeap().findKthLargestNum(a, k)print('kth largest num is',res)