左神算法基础班第一周

异或的性质及扩展

将异或看成“无进位相加”。那么，它的一些性质就好理解了。

1. 0 ^ N = N，0 与任何数异或都是这个数本身。N ^ N = 0，任何数与自己异或都为 0。

2. 异或运算满足交换律和结合律

3. 不用额外变量即可交换两个数

int a = 7;
int b = 103;

a = a ^ b;
b = a ^ b;
a = a ^ b;

证明：把第4行代入第5行，b = (a ^ b) ^ b = a。把第4行和第5行的结果代入第6行，a = (a ^ b) ^ a = b

4. 一个数组中，有1种数出现了奇数次，其他都出现了偶数次。怎么找到这种数。 :sparkles:

力扣 136，剑指offer 56

用一个初值为 0 的变量去异或数组中的每一个元素，最后的结果就是出现了奇数次的数。

原因：因为异或运算满足交换律，只要是出现了偶数次的数，那么其异或的结果必为0；出现了奇数次的数，异或的结果必为它本身。

力扣 136题

int singleNumber(vector<int>& nums) {
  int ero = 0;
  for(auto a : nums){
    ero ^= a;
  }

  return ero;
}

5. 一个数组中，有2种数（假设是 a 和 b）出现了奇数次，其他都出现了偶数次。怎么找到这2种数。 :sparkles:

力扣 260 题

用 eor 去异或数组中的每一个元素，最后的结果一定是 a ^ b。因为 a 和 b 一定不相等（两种数），即 eor 一定不是 0。

那么，eor 的二进制位上，一定有 1 位是 1，假设最右边的为 1 的是第 x 位。

提取一个不为 0 的数里最右侧的1：int x = eor & (~eor + 1);

那么，在 x 位上，a 和 b一定是不同的。这样就把数组中所有的数分成了两类：一类是第 x 位上是 1 的数，一类是第 x 位上是 0 的数。不妨设 a 的第 x 位上是1，b 的第 x 位上是 0。

定义一个新的变量 int eor' = 0;，与数组中第 x 位为 1 的变量进行异或，那么得到的数一定是 a。即，此时 eor' = a。要想得到 b，用eor ^ eor' = (a ^ b) ^ a = b即可。

6. 一个数组中，有一种数出现了 1 次，其他都出现了 3 次。怎么找到这一种数？

力扣 137 题

// 该解法是个通用解，只需改变取余的数，即可解决出现几次的类似题，但不是最优
int singleNumber(vector<int>& nums){
  int total = 0, ans = 0;
  for (int i = 0; i < 32; i++){
    for (auto num: nums){
      total += (num >> i) & 1;			// 1的二进制是 00000001，不是11111111，这么做的原因是把答案数该位上的1保留下来
    }

    if (total % 3){
      ans |= (1 << i);
    }
    total = 0;
  }

  return ans;
}

最优解仍然是按照位运算的思路解。

int singleNumber(vector<int>& nums) {
    int a = 0, b = 0;
    for (int num: nums) {
        b = ~a & (b ^ num);
        a = ~b & (a ^ num);
    }
    return b;
}

递归

给一个数组 arr[100]，找最大值。

int findMax(vector<int> &a, int left, int right){
  if (left == right){
    return a[left];
  }
  else{
    int mid = left + ((right - left) >> 1);	// 中点为什么这么写？
    int maxLeft = findMax(a, left, mid);
    int maxRight = findMax(a, mid+1, right);
    return maxLeft > maxRight ? maxLeft : maxRight;
  }
}

求中点为什么要写 L + ((L - R) >> 1) 不写 (L + R) / 2 呢？首先， L + R 可能会溢出；其次，除 2 没有移位的速度快。

Master 公式

怎么确定一个递归行为的时间复杂度？

假设在 L 到 R 上是 N 的数据规模，那么时间复杂度可以写作 T(N)（在数据规模为N的情况下时间复杂度为）。

首先看代码中子过程递归调用的部分，然后再看其他部分

$T(N) = T(\frac{N}{2}) + T(\frac{N}{2}) + O(1) = 2T(\frac{N}{2}) + O(1)$

Master 公式模型如下：

$T(N) = aT(\frac{N}{b}) + O(N^d)$

Master 指的是某一类递归行为：

子过程缩小的规模都是 $\frac{N}{b}$，而且子过程被调用了 $a$ 次；除去调用子过程之外，剩下的时间复杂度为 $(N^d)$。这一类模型，称为 Master 公式。注意，子问题一定是等规模的，不然用不了 Master 公式。

参考 数据结构-复杂度分析 中的分治法主定理。

1. 如果 $\log_b a < d$，那么$T(n) = O(N^d)$
2. 如果 $\log_b a > d$，那么$T(n) = O(N^{\log_b a})$
3. 如果 $\log_b a = d$，那么$T(n) = O(N^d \times \log N)$

由此来看，Master 公式是分治法主定理的一种特殊情况。

归并排序

Merge 的过程，准备另外的一个与待排数组空间一样大的数组，原数组用两个指针，策略是谁小拷贝谁。

ps: 有些头文件如 SortLogMachine.h, LeetcodePrint.h 是为了方便测试和调试而写的，里面的一些函数 generateRandomVector 等的实现见 lushuangning/AlgorithmStudy

#include <iostream>
#include <vector>
#include "SortLogMachine.h"
#include "LeetcodePrint.h"

void merge(vector<int> &arr, int l, int m, int r);

void mergeSort(vector<int> &arr, int l, int r) {
  if (l == r) {
    return;
  }

  int mid = l + ((r - l) >> 1);
  mergeSort(arr, l, mid);
  mergeSort(arr, mid+1, r);
  merge(arr, l, mid, r);
}

void merge(vector<int> &arr, int l, int m, int r) {
  vector<int> help(r - l + 1);
  int lPtr = l, rPtr = m+1, i = 0;

  while (lPtr <= m && rPtr <= r) {
    help[i++] = arr[lPtr] <= arr[rPtr] ? arr[lPtr++] : arr[rPtr++];
  }

  while (lPtr <= m) {
    help[i++] = arr[lPtr++];
  }

  while (rPtr <= r) {
    help[i++] = arr[rPtr++];
  }

  for (size_t i = 0; i < help.size(); i++) {
    arr[l+i] = help[i];
  }
}

int main() {
  vector<int> vec = generateRandomVector(10, 0, 100);

  show1DVector(vec);

  cout << "\n";

  process(vec, 0, vec.size() - 1);

  show1DVector(vec);

  return 0;
}

该排序的 Master 公式为：

$T(N) = T(\frac{N}{2}) + T(\frac{N}{2}) + O(N) = 2T(\frac{N}{2}) + O(N)$

根据 Master 公式，时间复杂度为：$O(N \times \log N)$，空间复杂度$O(N)$

归并排序的扩展

小和问题和逆序对问题很重要，每年面试题必出。 :exclamation:

小和问题 :sparkles:

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。

换个解释：也可以说，每个数 $x$ 的右边有多少个数比它大，该数组的小和里面就会有多少个 $x$ 相加。（只有左边数小于右边数的时候，会产生小和）。

归并时，相等的时候，优先拷贝右组的数

#include <iostream>
#include <vector>
#include "SortLogMachine.h"
#include "LeetcodePrint.h"

using namespace std;

int merge(vector<int> &vec, int l, int m, int r) {
  int p1 = l, p2 = m + 1, i = 0, res = 0;

  vector<int> help(r - l + 1);
  while (p1 <= m && p2 <= r) {
    res += vec[p1] < vec[p2] ? (r - p2 + 1) * vec[p1]: 0;	// 求小和的过程
    help[i++] = vec[p1] < vec[p2] ? vec[p1++] : vec[p2++];	// merge 的过程。注意这里与归并排序有区别，这里是小于
  }

  while (p1 <= m) {
    help[i++] = vec[p1++];
  }

  while (p2 <= r) {
    help[i++] = vec[p2++];
  }

  for (size_t i = 0; i < help.size(); i++) {
    vec[l + i] = help[i];
  }

  return res;
}

int smallSum(vector<int>& vec, int l, int r) {
  if (l == r) {
    return 0;
  }
  int m = l + ((r - l) >> 1);

  return smallSum(vec, l, m) + smallSum(vec, m + 1, r) + merge(vec, l, m, r);
}

int main() {
  vector<int> vec = generateRandomVector(10, 0, 100);

  show1DVector(vec);

  cout << smallSum(vec, 0, vec.size() - 1);

  return 0;
}

逆序对问题 :sparkles:

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对。请返回逆序对的数量

小和问题是一个数右边有多少个数比它大，逆序对问题是一个数右边有多少个数比它小。

堆排

堆是比堆排序重要的多的内容，要先学好堆。

堆的结构：

物理结构：数组

逻辑结构：有特殊标准的完全二叉树

对于数组的每一个位置 $i$，其左孩子的位置为 $2 \times i + 1$，右孩子的位置为 $2 \times i + 2$，父结点的位置为 $\lfloor \frac{i-1}{2} \rfloor$。

void heapInsert(vector<int> &vec, int index) {
  // vec[0...index-1] 已经是大根堆了，某个数现在处在 index 位置，往上继续移动
  while ( vec[index] > vec[(index - 1) / 2] ) {
    // 交换
    vec[index] = vec[index] ^ vec[(index - 1) / 2];
    vec[(index - 1) / 2] = vec[index] ^ vec[(index - 1) / 2];
    vec[index] = vec[index] ^ vec[(index - 1) / 2];

    index = ((index - 1) / 2 );
  }
}

// 堆调整
void heapify(vector<int> &vec, int index, int heapSize) {
  int left = index * 2 + 1;
  while (left < heapSize) { // 左孩子不越界
    // 右孩子也不越界，找到两个孩子中数值较大的那一个的下标
    // 如果没有右孩子，那下标就是左孩子的下标
    int max = left + 1 < heapSize && vec[left + 1] > vec[left] ? left + 1 : left;	

    // 父结点和较大孩子的值进行比较。找到值大的那一个的下标
    max = vec[max] > vec[index] ? max : index;
    if (max == index) {
      break;
    }
    vec[index] = vec[index] ^ vec[max];
    vec[max] = vec[index] ^ vec[max];
    vec[index] = vec[index] ^ vec[max];

    index = max;
    left = index * 2 + 1;
  }
}

void heapSort(vector<int> &vec) {
  int len = vec.size();
  int tmp;

  // 建堆，O(n logn)
  for (int i = 1; i < len; i++) {
    heapInsert(vec, i);
  }

  // pop的过程
  for (int i = len-1; i > 0; i--) {
    tmp = vec[len];
    vec[len] = vec[0];
    vec[0] = vec[len];
    heapify(vec, 0, i);
  }
}

建堆的过程时间复杂度是 $O(n \times \log n)$，如果用户一次性将所有数都给出，建堆的时间复杂度可以降低到 $O(n)$。

以完全二叉树为例

叶子层有 $\frac{N}{2}$ 个结点，每一个单独的结点都是一个堆，所做的操作只是 “看一眼”，$O(1)$ 的时间复杂度。

往上一层，有 $\frac{N}{4}$ 个结点。将每个结点 heapify() 一下，所做的操作是 $O(2)$ 的时间复杂度。

再往上一层，有$\frac{N}{8}$ 个结点。将每个结点 heapify() 一下，所做的操作是 $O(3)$ 的时间复杂度。

…

总的时间复杂度为

$$T(N) = \frac{N}{2} \times 1 + \frac{N}{4} \times 2 + \frac{N}{8} \times 3 + \frac{N}{16} \times 4 + ... \\ 2T(N) = N + \frac{N}{2} \times 2 + \frac{N}{4} \times 3 + \frac{N}{8} \times 4 + ...$$

错位相减

$$T(N) = N + \frac{N}{2} + \frac{N}{4} + \frac{N}{8} + \frac{N}{16} + ...$$

收敛于 $c \times O(N)$，其中 $c$ 是一个常数。

对应的代码为：

void heapSort(vector<int> &vec){
  int len = vec.size();
  int tmp;

  // 建堆，O(N logN)
  // for (int i = 1; i < len; i++)
  // {
  // 	heapInsert(vec, i);
  // }

  // 更低的时间复杂度建堆方法，O(N)
  for (int i = len-1; i >= 0; i--) {
    heapify(vec, i, len);
  }

  // O(N logN)
  for (int i = len-1; i > 0; i--) {
    tmp = vec[len];
    vec[len] = vec[0];
    vec[0] = vec[len];
    heapify(vec, 0, i);
  }
}

堆排序扩展题 :sparkles:

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离不超过 k （由参数给出），并且 k 相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

思路：

使用一个大小为 k+1 的小根堆。将数组前 k+1 个数先扔到小根堆里，然后弹出一个最小值。由于每个元素的距离距离不会超过 k，因此弹出的这个数将会是整个数组中的最小值。然后将数组中剩余的数依次加入小根堆并依次弹出。这样，使用一个大小为 k+1 的小根堆即可解决该问题

荷兰国旗问题 :sparkles:

问题一

给定一个数组 arr 和一个数 num，请把小于等于 num 的数放在数组的左边，大于 num 的数放在数组的右边。要求额外空间复杂度 $O(1)$，时间复杂度 $O(N)$。

思路：

划定一个 小于等于区，一开始的大小为0，index 从0开始。

• 若 arr[index] <= num，则 arr[index] 与 小于等于区 的后面一个数交换，并且 小于等于区 扩大 1，index 后移
• arr[index] > num，则 index 自增。

直到 index 遍历完整个数组。

问题二（荷兰国旗问题）

给定一个数组 arr 和一个数 num，请把小于 num 的数放在数组的左边，等于 num 的数放在数组的中间，大于 num 的数放在数组的右边。要求额外空间复杂度 $O(1)$，时间复杂度 $O(N)$。

tips: 因为荷兰国旗有三种颜色，所以把这种直观的分为三块的问题称为荷兰国旗问题。

思路：

• arr[index] < num

  arr[index] 和 小于区 下一个数交换，然后 小于区 向右扩一个位置，index 自增

• arr[index] = num

  index 自增

• arr[index] > num

  arr[index] 和 大于区 的前一个数交换，然后 大于区 向左扩一个位置，index 停在原地不动

index 与 大于区 的左边界重合的时候，循环停止。

力扣 75 题，我的代码

快速排序

1.0 版本

借鉴刚才的荷兰国旗问题，选取数组中最后一个元素作为 num，然后将数组划分为三块：

左边的 小于等于区，中间的 大于区 和数组最后一个元素 num。将 num 与 大于区 的最左边的元素作交换。此时，num 所在的位置就是数组有序后的位置。然后对 小于等于区 和 大于区 分别做递归操作。

2.0 版本

将所有等于 num 的元素放中间，递归时 小于区 的右边界和 大于区 的左边界。比 1.0 版本优化了常数项的时间。如果数组中没有重复的值，那 2.0 版本就是 1.0 版本。

前两个版本的复杂度分析

时间复杂度$O(N^2)$

数组已经有序是最坏情况：$O(N^2)$

平均时间复杂度：$O(N \log N)$

3.0 版本：随机快排，教材上的版本

改进之处：等概率随机选一个数作划分值和最后一个数做交换，然后再排。坏情况跟好情况都是概率时间，每一种情况都占 $\frac{1}{N}$，在数学上可证明出它的时间复杂度能收敛到$O(N \log N)$

----------------------------to be continued--------------------------------