23王道数据结构代码题全解（二）

计划更新23王道数据结构所有课后代码习题的实现，虽然考试写的一般都是伪代码，但是强迫症的我还是全部实现了一遍，仓库在这里

代码全部是用 C++ 写的，都可以编译运行，包含暴力解和最优解。

持续更新，目前更新进度：

• 线性表
• 链表
• …

仅供参考！ 会包含一些考试不让写的语法，可能也会有一些错误。

2.2.3, 08

• 暴力方法，再开一个数组，然后就是循环！
• 一次循环不行，两次!
• 参数 m 和 n 为两个线性表的长度
• 时间复杂度O(m+n)，空间复杂度O(m+n)

void change(SqList &list, int m, int n) {
  // 前一个线性表[0, m-1], 后一个[m, m+n-1]
  SqList copied = list;
  int k = -1;
  for (int i = m; i < m+n; i++) {
    copied.data[++k] = list.data[i];
  }
  for (int i = 0; i < m; i++) {
    copied.data[++k] = list.data[i];
  }
  list = copied;
}

• 当然还有一种四两拨千斤的方法，可以先逆置整个数组，再分别逆置其中的两个线性表
• 比如说[1, 2, 3, 4]逆置成[4, 3, 2, 1]，然后其中一个线性表[4, 3]逆置成[3, 4]，另一个[2, 1]逆置成[1, 2]，最后结果就是[3, 4, 1, 2]
• 时间复杂度O(m+n)，空间复杂度O(1)

// 逆置，跟第二题类似, l=left, r=right
void reverse(SqList &list, int l, int r) {
  if (l > r || r > list.length) return;

  int mid = (l + r) / 2;
  // 注意边界
  for (int i = 0; i <= mid - l; i++) {
    swap(list.data[l+i], list.data[r-i]);
  }
}

void change2(SqList &list, int m, int n) {
  // 注意参数
  reverse(list, 0, m+n-1);
  reverse(list, 0, n-1);
  reverse(list, n, m+n-1);
}

2.2.3, 09

• 递增有序，暴力循环
• 需要考虑很多边界条件，容易出错
• 时间复杂度O(n)，空间复杂度O(1)

void find_x2(SqList &list, int x) {
  // 1.二分找x
  int low = 0, high = list.length - 1, mid;
  while (low <= high) {
    mid = (low + high) / 2;
    if (list.data[mid] == x) break;
    else if (list.data[mid] < x) low = mid + 1;
    else high = mid - 1;
  }

  // 2.找到了
  if (list.data[mid] == x && mid != list.length - 1) {
    swap(list.data[mid], list.data[mid + 1]);
    return;
  }
  
  // 3.没找到, 此时low>high
  list.length++;
  int i = list.length - 2;
  while (i > high) {
    list.data[i + 1] = list.data[i]; 
    i--;
  }
  list.data[i + 1] = x;
}

• 优化，使用二分查找，不需要特别记录i的值
• 当查找失败时，high 会记录到最后一个小于x的元素
• 时间复杂度O(logn)，空间复杂度O(1)

void find_x2(SqList &list, int x) {
  int low = 0, high = list.length - 1, mid;
  while (low <= high) {
    mid = (low + high) / 2;
    if (list.data[mid] == x) break;
    else if (list.data[mid] < x) low = mid + 1;
    else high = mid - 1;
  }

  // 找到了并且不是最后一个元素
  if (list.data[mid] == x && mid != list.length - 1) {
    swap(list.data[mid], list.data[mid + 1]);
    return;
  }

  // 没找到
  list.length++;
  int i = list.length - 2;
  while (i > high) {
    list.data[i + 1] = list.data[i]; 
    i--;
  }
  list.data[i + 1] = x;
}

2.2.3, 10

• 这个真题跟第8题基本一样，我们可以直接copy过来改一下参数
• 首先就是暴力求解，新开一个数组，分别复制进去（把结构体改成数组是一样的）
• 这样的时间复杂度是O(n)，空间复杂度也是O(n)
• 为了节省空间，也可以创建一个大小为p的数组暂存前一个数组[0, p-1]，原数组整体左移后再依次放回，这样的空间复杂度会降到O§

void change(SqList &list, int p, int n) {
  // 1.左右两个数组分别是[0, p-1], [p, n-1]
  SqList copied = list;
  int k = -1;
  // 2.分别复制进去
  for (int i = p; i < n; i++) {
    copied.data[++k] = list.data[i];
  }
  for (int i = 0; i < p; i++) {
    copied.data[++k] = list.data[i];
  }
  // 3.新换旧
  list = copied;
}

• 四两拨千斤，整体逆置，再分别逆置
• 比如说[1, 2, 3, 4]逆置成[4, 3, 2, 1]，然后其中一个数组[4, 3]逆置成[3, 4]，另一个[2, 1]逆置成[1, 2]，最后结果就是[3, 4, 1, 2]
• 时间复杂度O(n)，空间复杂度O(1)

void reverse(SqList &list, int l, int r) {
  if (l > r || r > list.length) return;

  for (int i = 0; i < (r-l+1)/2 ; i++) {
    swap(list.data[l+i], list.data[r-i]);
  }
}

void change2(SqList &list, int p, int n) {
  // 注意参数
  reverse(list, 0, n);
  reverse(list, 0, p);
  reverse(list, p, n);
}

2.2.3, 11

• 找到两个有序序列合并后的中位数，那暴力解就直接合并呗
• 可以把第7题直接抄过来，然后返回 (A.length + B.length)/2 位置上的数即可
• 然后你会发现并不需要合并全部，也不需要一个辅助表来存储数据，只需要循环到这个位置就可以了
• 注意题目中要求，mid 应该等于 (A.length + B.length - 1) / 2
• 时间复杂度O(n)，空间复杂度O(1)

int merge(SqList A, SqList B) {
  int i = 0, j = 0, k = -1, mid = (A.length + B.length - 1) / 2;
  
  // 条件也不需要，因为我们找到中间值就会直接return
  while (1) {
    ++k;
    if (A.data[i] <= B.data[j]) {
      if (k == mid) return A.data[i];
      i++;
    } else {
      if (k == mid) return B.data[j];
      j++;
    }
  }
}

• 也可以直接循环到 mid 处，不需要每次都判断一次 ==mid

int merge2(SqList A, SqList B) {
  int i = 0, j = 0, mid = (A.length + B.length - 1) / 2 ;
  while (i+j < mid) {
    if (A.data[i] <= B.data[j]) i++;
    else j++;
  }
  return A.data[i] < B.data[j] ? A.data[i] : B.data[j];
}

• 考试不建议最优解，时间成本太高(大佬除外)，毕竟暴力解最多好像只有5分差距，没必要
• 我这里就不写了，可以看一下王道答案

2.2.3, 12

• 找重复元素，且该元素个数要超过数组的一半，所以一个数组最多只有一个主元素
• 暴力，就是拿空间换时间，类似桶排序
• 开一个新数组，新数组的下标对应元素值，值对应元素个数（因为数的范围是确定的）
• 时间复杂度O(n)，空间复杂度O(n)

int find_main(SqList list) {
  // 1.初始化一个全为0的数组
  int tmp[list.length] = {0};

  // 2.新数组的下标对应元素值，值对应元素个数
  for (int i = 0; i < list.length; i++) {
    tmp[list.data[i]]++;
  }

  // 3.遍历找出主元素
  for (int i = 0; i < list.length; i++) {
    if (tmp[i] > list.length / 2 ) 
      return i;
  }

  // 4.没找到返回-1
  return -1;
}

• 第二种方法：我们先排好序再找主元素
• 记录每个元素出现的次数，如果后面的数不是重复元素，就判断当前元素是否为主元素
• 因为用了快排，时间复杂度O(nlogn)，空间复杂度O(logn)
• 总分13分，这个解最高可以拿11分，所以不要强求最优解

int find_main2(SqList list) {
  // 1.快排
  sort(list.data, list.data+list.length);

  // 2.记录每个元素出现的次数，找到主元素
  int cnt = 1;
  for (int i = 0; i < list.length - 1; i++) {
    if (list.data[i+1] == list.data[i]) {
      cnt++;
    } else {
      if (cnt > list.length / 2)
        return list.data[i];
      cnt = 1;
    }
  }
  return -1;
}

• 这道题考试的时候（应该大概也许）可以不写跟题目无关的排序的具体实现
• 因为快排每次递归需要的空间是固定的，递归层数即为空间复杂度，故快排的平均空间复杂度为O(logn)
• 快排的实现如下：

void quick_sort(int l, int r) {
  if (l == r) return; 
  
  int x = a[(l+r)/2];     // 1.枢纽元素
	
  // 2.分成两块
  int i = l-1, j= r+1;
  while (i < j) {
    while (a[++i] < x);		// 找到左边比x大的元素
    while (a[--j] > x);		// 找到右边比x小的元素
    if (i < j) swap(a[i], a[j]); 	// 互换
  }
	
  // 3.递归
  quick_sort(l, j);
  quick_sort(j+1, r);
}

• 最优解，对对碰
• 因为主元素个数要超过数组的一半，它就可以抵掉所有其他元素且有剩余
• 时间复杂度O(n)，空间复杂度O(1)

int find_main3(SqList list) {
  int c, cnt = 1;
  c = list.data[0];

  // 1.选定候选主元素
  for (int i = 1; i < list.length; i++) {
    if (list.data[i] == c) cnt++;
    else {
      if (cnt > 0) {
        cnt--;
      } else {
        c = list.data[i];
        cnt = 1;
      }
    }
  }

  // 2.统计实际数量
  if (cnt > 0) {
    cnt = 0;
    for (int i = 0; i < list.length; i++)
      if (list.data[i] == c) 
        cnt++;
  }
  
  // 3.确认主元素
  if (cnt > list.length / 2) return c;
  return -1;
}

2.2.3, 13

• 找最小正整数，所以不需要管负数
• 想法还是跟12题第一种解法一样，类似桶排序
• 开一个新数组，下标对应元素值，值对应元素是否出现
• 时间复杂度O(n)，空间复杂度O(n)，竟然已经是最优解了？

int find_miss_min(SqList list) {
  // 1.初始化一个全为0的数组
  int tmp[list.length] = {0};

  // 2.下标对应元素值，值对应元素是否出现
  for (int i = 0; i < list.length; i++) {
    if (list.data[i] > 0 && list.data[i] <= list.length)
      tmp[list.data[i]]++;
  }

  // 3.找到最小正整数
  int i;
  for (i = 1; i < list.length; i++) {
    if (tmp[i] == 0) 
      return i;
  }
  return i;
}

2.2.3, 14

• 暴力，直接三重循环！
• 一个一个算，找到最小的
• 时间复杂度O(n³)，时间复杂度O(1)

int find_min_distance(int A[], int B[], int C[], int n1, int n2, int n3) {
  int dmin = INT_MAX, d;
  for (int i = 0; i < n1; i++) {
    for (int j = 0; j < n2; j++) {
      for (int k = 0; k < n3; k++) {
        // 计算距离
        d = abs(A[i] - B[j]) + abs(B[j] - C[k]) + abs(C[k] - A[i]);
        // 更新最小值
        if (d < dmin) dmin = d;
      }
    }
  }
  return dmin;
}

• 众所周知，绝对值体现的是数轴上的距离

• 当 a=b=c 时，距离最小

• 当 a<=b<=c 时，如图所示

• 决定D大小的因素就是c和a的距离，所以我们每次固定c找一个使距离最小的a就可以了

• 时间复杂度O(n)，空间复杂度O(1)

// n1是否是三个数中的最小值
bool find_min(int n1, int n2, int n3) {
  if (n1 <= n2 && n1 <= n3) return true;
  return false;
}

int find_min_distance2(int A[], int B[], int C[], int n1, int n2, int n3) {
  int dmin = INT_MAX, d, i = 0, j = 0, k = 0;
  while(i < n1 && j < n2 && k < n3) {
    // 计算距离
    d = abs(A[i] - B[j]) + abs(B[j] - C[k]) + abs(C[k] - A[i]);
    // 更新最小值
    if (d < dmin) dmin = d;
		
    if (find_min(A[i], B[j], C[k])) i++;
    else if (find_min(B[j], C[k], A[i])) j++;
    else k++;
  }
  return dmin;
}