面试必刷TOP101：二分查找/排序（17-22，Python实现）

17.二分查找（小试牛刀）

17.1 二分法

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = int((left+right) / 2)
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(logn)，对长度为 n 的数组进行二分，最坏情况就是取 2 的对数。
空间复杂度：O(1)，无额外空间。

17.2 遍历查找法

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        for i in range(0,len(nums)):
            if nums[i] == target:
                return i
        return -1
1
2
3
4
5
6

时间复杂度：O(n)，遍历一次数组。
空间复杂度：O(1)，无额外空间。

18.二维数组中的查找（小试牛刀）

18.1 二分查找

class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        if len(array) == 0:
            return False
        m = len(array)
        if len(array[0]) == 0:
            return False
        n = len(array[0])
        for i in range(m-1,-1,-1):
            for j in range(0,n):
                if array[i][j] > target:
                    i = i - 1
                elif array[i][j] < target:
                    j = j + 1
                else:
                    return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

两个 for 循环也可以换成 while。

i = m - 1; j = 0
while i >= 0 and j < n:
1
2

时间复杂度：O(m+n)，最多经过一行一列。
空间复杂度：O(1)，没有使用额外空间。

18.2 暴力遍历

时间复杂度：O(nm)，二维数组的遍历。
空间复杂度：O(1)，没有使用额外空间。

19.寻找峰值

19.1 二分查找

class Solution:
    def findPeakElement(self , nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = int((left+right)/2)
            if nums[mid] > nums[mid+1]:
                right = mid
            else:
                left = mid + 1
        return right
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：O(logn)，二分法最坏情况为O(logn)。
空间复杂度：O(1)，无额外空间使用。

20.数组中的逆序对（小试牛刀）

20.1 暴力法（不会AC）

class Solution:
    def InversePairs(self , data: List[int]) -> int:
        kmod = 1000000007
        num = 0
        n = len(data)
        for i in range(0,n):
            for j in range(i+1,n):
                if data[i] > data[j]:
                    num = num + 1
                    num = num % kmod
        return num
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：O(N^2)，对于此题显然超时
空间复杂度：O(1)

20.2 归并排序法

class Solution:
    def MergeSort(self, left: int, right: int, nums: List[int]) -> int:
        if left >= right:
            return 0
        mid = int((left+right)/2)
        count = 0
        count = self.MergeSort(left, mid, nums) + self.MergeSort(mid+1, right, nums)
        temp = [0 for i in range(0,right-left+1)] # 构建一个空数组，其大小 = 待合并的两个数组大小之和，最后会是一个有序数组
        i = left; j = mid + 1; p = 0 # 左边的指针、右边的指针、temp中的指针
        while i <= mid and j <= right: # 左边部分的边界mid，右边部分的边界right。这个while实际就是将两个部分，进行合并的时候排序。
            if nums[i] < nums[j]:
                temp[p] = nums[i]
                p = p + 1
                i = i + 1
            else:
                count = (count + (mid-i+1)) % 1000000007
                temp[p] = nums[j]
                p = p + 1
                j = j + 1
        # 当两个序列合并时，左边或者右边先通过指针移动完毕，全复制进temp后，就需要将另一边的数据，也全部复制给temp。
        if i <= mid:
            while i <= mid:
                temp[p] = nums[i]
                p = p + 1
                i = i + 1
        if j <= right:
            while j <= right:
                temp[p] = nums[j]
                p = p + 1
                j = j + 1
        for k in range(0, right-left+1): # 将合并好的数组再复制回nums，以保证有序。
            nums[left+k] = temp[k]
        return count
    def InversePairs(self , data: List[int]) -> int:
        n = len(data)
        return self.MergeSort(0, n-1, data)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

21.旋转数组的最小数字（小试牛刀）

21.1 二分法

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        left = 0
        right = len(rotateArray) - 1
        while left < right:
            mid = int((left+right)/2)
            if rotateArray[mid] > rotateArray[right]:
                left = mid + 1
            elif rotateArray[mid] == rotateArray[right]:
                right = right - 1
            else:
                right = mid
        return rotateArray[left]
1
2
3
4
5
6
7
8
9
10
11
12
13

21.2 遍历查找

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        res = rotateArray[0]
        for i in range(0,len(rotateArray)):
            res = min(res,rotateArray[i])
        return res
1
2
3
4
5
6

22.比较版本号（小试牛刀）

22.1 分割查找法

class Solution:
    def compare(self , version1: str, version2: str) -> int:
        a = version1.split('.')
        b = version2.split('.')
        i = 0
        for i in range(max([len(version1),len(version2)])):
            if i < len(a):
                num1 = int(a[i])
            else:
                num1 = 0
            if i < len(b):
                num2 = int(b[i])
            else:
                num2 = 0
            if num1 > num2:
                return 1
            if num1 < num2:
                return -1
        return 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度：O(max(n, m))，其中 m 和 n 分别为两个字符串的长度，流输入和 split 相当于遍历字符串，复杂度选取较高值。
空间复杂度：O(max(n, m))，使用了记录分割后修订号的数组，最坏长度为二者原本字符串长度最大值。

22.2 双指针遍历截取

class Solution:
    def compare(self , version1: str, version2: str) -> int:
        m = len(version1)
        n = len(version2)
        i = 0 ; j = 0
        while i < m or j < n:
            num1 = 0
            while i < m and version1[i] != '.':
                num1 = num1 * 10 + int(version1[i])
                i = i + 1
            i = i + 1 # 跳过点
            
            num2 = 0
            while j < n and version2[j] != '.':
                num2 = num2 * 10 + int(version2[j])
                j = j + 1
            j = j + 1 # 跳过点
        
            if num1 > num2:
                return 1
            if num1 < num2:
                return -1
        return 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度：O(max(n, m))，其中 m 和 n 分别为两个字符串的长度，遍历两个字符串，复杂度选取较高值。
空间复杂度：O(1)，常数级变量，无额外辅助空间。