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(n3)，时间复杂度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; } 复制代码
- 顺序表已经更完，明天继续更新链表
