[LeetCode解题报告] 1464. 数组中两元素的最大乘积（BFPRT）

那么为什么复杂度是*O(n)*呢？

8. 首先要证明每次取得中位数，它的位置很靠中间：一定在30%~70%这个位置之间，也就是说最多有70%的数比它小，最多有70%的数比它大。
9. 每次find_mid时，找到的是中位数数组的中位数，这个中位数数组的长度是n//5,
	- 这个数组里有n//10个数比它小,
	- 而这些比它小的数都是原来5人组的中间值，所以每组里还有俩比它小的数n//10*2，所以共有n*3//10个数比它小。
10.因此，最坏是按70%的速度退化的。相当于每次只能搞定30%。 
11.时间复杂度 T(N) = T(N/5) + T(7N /10) + O(N)=T(9N/10)+O(n)。
12.套主项定理：a=1,b=10/9,f(n)=O(n)明显对数log(10/9,1)结果小于1，因此得：T(n) = O(n)
13.可以参考算法导论第九章。

对了，我试了，还是排序快！

最坏时间复杂度O(n)

线段树。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        def insert_sort(arr,l,r):
            for i in range(l,r):
                x = arr[i+1]
                j = i 
                while x < arr[j] and j >= l:
                    arr[j+1] = arr[j]
                    j -= 1
                arr[j+1] = x
        def find_mid(arr,l,r):
            if l+1 >= r:
                return l 
            c = l
            for i in range(l,r-5,5):
                insert_sort(arr,i,i+4)
                arr[c],arr[i+2] = arr[i+2],arr[c]
                c += 1
            x = l+(r-l+1)//5*5
            insert_sort(arr,x,r)
            m = (x+r)//2
            arr[c],arr[m] = arr[m],arr[c]
            return find_mid(arr,l,c)        
        def partion(arr,l,r):
            pivot = arr[l]
            while l < r:
                while arr[r] >= pivot and l < r:
                    r -= 1
                arr[l] = arr[r]
                while arr[l] <= pivot and l < r:
                    l += 1
                arr[r] = arr[l]
            arr[l] = pivot
            return l                   
        def bfprt(arr,k,l,r):            
            # 在[l,r]里找到一个数，这个数应放在下标k,使k左边都小于arr[k],k右边都大，那么这个数就是第k小(从0开始数)               
            find_mid(arr,l,r)  # 把中位数放到l上作为pivot
            m = partion(arr,l,r)  # 把pivot放在应在的位置m上，同时使m左边都小于arr[m],m右边都大于等于arr[m]
            if m == k:
                return arr[m]
            elif m > k:
                return bfprt(arr,k,l,m-1)
            else:
                return bfprt(arr,k,m+1,r)            
        n = len(nums)
        bfprt(nums,n-2,0,n-1)
        # print(nums)
        return (nums[n-1]-1) * (nums[n-2]-1)

1. 主项定理