任务：

1. 学习周期：8.17 — 8.21 号，共计 5 天。

2. 学习专题：数组。主要题目类型主要有查找、排序。其中数组需要的技巧相对多一些。比如二分法、子数组、双指针、滑动窗口、快排变形等等，其中的快排变形、双指针是最最常考的点，一定要掌握。

3. 训练题目：标红的重点再多巩固巩固

• 21: 调整数组顺序，使奇数位于偶数前面

• 3：数组中重复的数字

• 4 : 二维数组中的查找

• 11 ：旋转数组的最小数字

• 39：数组中出现次数超过一半的数字

• 51: 数组中的逆序对

1. 链表复习：

• 52 两个链表的第一个公共节点

• 35 复杂链表的复制

21. 调整数组顺序，使奇数位于偶数前面(8.17)

1. 思路

• 首先要遍历数组，判断是奇数还是偶数
• 辅助数组法
  • 申请两个空数组，一个放奇数，一个放偶数，最后合并一下
  • 如果使用一个数组，把奇数放在前面，把偶数放到最后
• 交换位置
  • 本质也是双指针
• 双指针
  1. 指针 i 从左向右寻找偶数
  2. 指针 j 从右向左寻找奇数
  3. 将 偶数 nums[i]和 奇数 nums[j] 交换

2. 辅助数组法

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        num1=[]
        num2=[]
        for i in nums:
            if i%2!=0:
                num1.append(i)
            else:
                num2.append(i)
        return num1+num2

• 换成一个数组

  class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        num1=[]
        for i in nums:
            if i%2!=0:
                num1.insert(0,i)
            else:
                num1.append(i)
        return num1

3. 交换位置

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        i = 0 
        for j in range(len(nums)):
            if nums[j]%2 == 1:
                nums[i],nums[j] = nums[j],nums[i]
                i+=1
        return nums

4. 双指针

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        m,n = 0,len(nums)-1
        while m<n:
            if nums[m]%2 == 0:
                nums[m],nums[n] = nums[n],nums[m]
                n -= 1
            else:
                m += 1
        return nums

5. 总结

这道题可以使用辅助数组和双指针，第二种交换方法本质也是双指针，只不过一个双指针在俩端，一个在一端，需要注意在list末尾添加元素时不可以使用insert(-1,i)，只能使用append(i)

3. 数组中重复的数字(8.18)

1. 思路

• set/字典
  • 创建一个set，遍历一遍数组，遍历时判断，是否在set中，
  • 如果在，返回，不在，添加到set中，如果遍历一遍没有，返回-1
  • dict也可以，原理一样
• 排序
  • 进行排序
  • 然后看是否有重复

• 原地置换

  • 题目说：在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内
  • 可遍历数组并通过交换操作，使元素的 索引 与 值 一一对应
  • 如果出现了第二次nums[x]=x，就代表出现了重复

    2. set/字典

    class Solution:
    def findRepeatNumber(self, nums):
       dic = set()
       for i in nums:
           if i in dic:
               return i
           dic.add(i)
       return -1

    3. 排序

    class Solution:
    def findRepeatNumber(self, nums):
       nums.sort()
       pre = nums[0]
       for i in nums:
           if pre == nums[i]:
               return i
           pre = nums[i]
       return -1

    4. 原地置换

    class Solution:
    def findRepeatNumber(self, nums):
       i = 0
       while i < len(nums):
           if nums[i] == i:
               i += 1
               continue
           if nums[nums[i]] == nums[i]:
               return nums[i]
           nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        return -1

    5. 总结

• 比较容易想到set这个解法，在判断链表是否有环也用到了set这种方法

• 排序也比较好
• 觉得面试官应该会比较喜欢最后原地置换的方法，看题解才想到
• 使用原地置换充分使用了题目给出的条件，其他方法是不需要这个条件的

4. 二维数组中的查找(8.19)

1. 思路

• 暴力
  • 直接遍历，没有难度，但是负责度高，没有充分利用条件
• 二分查找
  • 每一行进行二分查找，复杂度为O(nlogn)
• 线性查找
  • 从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。
  • 
  • 降低为O(m+n)的复杂度

    2. 暴力

    class Solution:
    def findNumberIn2DArray(self, matrix, target):
       for i in matrix:
           for j in i:
               if j == target:
                   return True
       return False

    3. 二分查找

    ```python class Solution: def findNumberIn2DArray(self, matrix, target): n = len(matrix) if n == 0:

       return False

    else:

       for i in range(n):
           left, right = 0, len(matrix[0]) - 1
           while left <= right:
               mid = (left + right + 1) // 2
               if matrix[i][mid] > target:
                   right = mid - 1
               elif matrix[i][mid] == target:
                   return True
               else:
                   left = mid + 1
       return False

<a name="TdlAb"></a>
### 4. 线性查找
```python
class Solution:
    def findNumberIn2DArray(self, matrix, target):
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        height = len(matrix)
        width = len(matrix[0])
        row = 0 
        col = width - 1
        while row < height and col >= 0:
            if matrix[row][col] > target:
                col = col - 1
            elif matrix[row][col] < target:
                row = row + 1
            else:
                return True
        return False

5. 总结

从暴力，二分查找到线性查找，复杂度从mn，nlogm，n+m逐渐减少，最优的是使用线性查找，可以类比二叉查找树，不容易想到

11. 旋转数组的最小数字

1. 思路

• 暴力
  • 直接返回数组的min
  • 将数组排序，返回nums[0]
  • 不是很好
• 找规律
  • 一个数组在一个位置进行反转
  • 这个列表分为两个升序子列表，那在这两个子列表的边界肯定会出现numbers[i]<numbers[i-1]numbers[i]<numbers[i−1]，这样返回numbers[i]numbers[i]
  • 遍历完没有返回值，那就说明这个列表是升序列表，只要返回第一个元素即可
  • 

• 二分查找

  • 设置 ii, jj 指针分别指向 numbers 数组左右两端，m = (i + j) // 2m=(i+j)//2 为每次二分的中点（ “//“ 代表向下取整除法，因此恒有 i \leq m < ji≤m<j ），可分为以下三种情况：
  • 当 numbers[m] > numbers[j]时： mm 一定在 左排序数组 中，即旋转点 xx 一定在 [m + 1, j][m+1,j] 闭区间内，因此执行 i = m + 1i=m+1；
  • 当 numbers[m] < numbers[j] 时： mm 一定在 右排序数组 中，即旋转点 xx 一定在[i, m][i,m] 闭区间内，因此执行 j = mj=m；
  • 当 numbers[m] == numbers[j] 时： 无法判断 mm 在哪个排序数组中，即无法判断旋转点 xx 在 [i, m][i,m] 还是 [m + 1, j][m+1,j] 区间中。解决方案： 执行 j = j - 1j=j−1 缩小判断范围

    2. 暴力

    class Solution:
    def minArray(self, numbers: List[int]) -> int:
       return min(numbers)

    class Solution:
    def minArray(self, numbers: List[int]) -> int:
       numbers.sort()
       return numbers[0]

    3. 找规律

    class Solution:
    def minArray(self, numbers: List[int]) -> int:
       for i in range(1,len(numbers)):
           if numbers[i]<numbers[i-1]:
               return numbers[i]
       return numbers[0]

    4. 二分查找

    class Solution:
    def minArray(self, numbers: [int]) -> int:
       i, j = 0, len(numbers) - 1
       while i < j:
           m = (i + j) // 2
           if numbers[m] > numbers[j]: i = m + 1
           elif numbers[m] < numbers[j]: j = m
           else: j -= 1
       return numbers[i]

    5. 总结

• 这道题比较好一点的方法是找规律和二分查找

• 这道题说明当数组旋转后也可以使用二分查找，但是当左右相同是需要做进一步的处理，不可以随便舍弃一边

39. 数组中出现次数超过一半的数字

1. 思路

• 字典统计
  • 遍历数组，添加到字典，重复元素加一
  • 判断这个值是否大于数组的一半，返回
• 数组排序
  • 对数组进行排序
  • 中位数一定是出现的次数超过一半的数字的值

• 摩尔投票

  • 正负抵消
  • 这个方法有的巧，假设第一个为众数，如果是众数就+1，不是就-1，如果为0就正负相肖，让后一个为众数，继续执行
  • 

    2. 字典统计

    class Solution(object):
    def majorityElement(self, nums):
       if not nums:
           return None
       if len(nums) == 1:
           return nums[0]
       write = {}
       for i in nums:
           if i not in write:
               write[i] = 1
           else:
               write[i] += 1
               if write[i] > (len(nums) / 2):
                   return i
       return None

    3. 数组排序

    class Solution(object):
    def majorityElement(self, nums):
       nums.sort()
       return nums[len(nums) // 2]

    4. 摩尔投票

    class Solution:
    def majorityElement(self, nums: List[int]) -> int:
       votes, count = 0, 0
       for num in nums:
           if votes == 0: x = num
           votes += 1 if num == x else -1
       for num in nums:
           if num == x: count += 1
       return x if count > len(nums) // 2 else 0

    5. 总结

• 在字典统计是要注意数组为一个元素的情况

• 摩尔投票有的巧，也是这个题的最佳解法，时间复杂度为O（n），空间复杂度为O（1）

51. 数组中的逆序对

1. 思路

• 暴力
  • 直接暴力，但是超时了

• 分治

  • 逆序对是归并排序的副产物
  • 归并排序实际上会把数组分成两个有序部分，我们不妨称其为左和右，归并排序的过程中会将左右两部分合并成一个有序的部分，对于每一个左右部分，我们分别计算其逆序数，然后全部加起来就是我们要求的逆序数。
  • 

  • 

    2. 暴力

    class Solution:
    def reversePairs(self, nums: List[int]) -> int:
       size = len(nums)
       if size < 2:
           return 0
       res = 0
       for i in range(0, size - 1):
           for j in range(i + 1, size):
               if nums[i] > nums[j]:
                   res += 1
       return res

    3. 分治

    ```python class Solution: def reversePairs(self, nums: List[int]) -> int: self.cnt = 0 def merge(nums, start, mid, end, temp):

       i, j = start, mid + 1
       while i <= mid and j <= end:
           if nums[i] <= nums[j]:
               temp.append(nums[i])
               i += 1
           else:
               self.cnt += mid - i + 1
               temp.append(nums[j])
               j += 1
       while i <= mid:
           temp.append(nums[i])
           i += 1
       while j <= end:
           temp.append(nums[j])
           j += 1
       for i in range(len(temp)):
           nums[start + i] = temp[i]
       temp.clear()

    def mergeSort(nums, start, end, temp):
        if start >= end: return
        mid = (start + end) >> 1
        mergeSort(nums, start, mid, temp)
        mergeSort(nums, mid + 1, end, temp)
        merge(nums, start, mid,  end, temp)
    mergeSort(nums, 0, len(nums) - 1, [])
    return self.cnt

```

4. 总结

• 还不是很理解分治和归并排序
• 这道题一上来的感觉很蒙，只想到暴力，看题解分治和树状数组，还是有些不是很明白