6.真题（只考虑次优解和暴力解）
6.1.数组
6.1.1.（2010）
（1）新建一个与arr数组等长的数组arr，先将arr的后p个元素依次存放到res数组的前p个元素中，然后再将arr的剩余元素依次存放到res的剩余元素中
int* Reverse(int arr[], int n, int p) { int *res = (int*)malloc(sizeof(n)); memset(a, 0, sizeof(int) * n); int i, j; for (i = n - p + 1, j = 0; i < n; i++, j++) res[j] = arr[i]; for (i = 0; i < n - p + 1; i++, j++) res[j] = arr[i]; }
（3）O（n），O（n）
6.1.2.（2011）
（1）都放入新数组中快速排序
int Partation(int arr[], int low, int high) { 随机将数组中某一元素和arr[low]交换 //快排优化 int pivot = arr[low]; //选择arr[low]为基准元素 while (low < high) { while (low < high && arr[high] >= pivot) high--; arr[low] = arr[high]; while (low < high && arr[low] < pivot) low++; arr[high] = arr[low]; } arr[low] = pivot; return low; } void QuickSort(int arr[], int low, int high) { if (low < high) { int pivotPos = Partation(arr, low, high); QuickSort(arr, low, pivotPos - 1); QuickSort(arr, pivotPos + 1, high); } } int GetMidNum(int A[], int B[], int len){ int* C = (int*)malloc((sizeof(int) * (2 * len)) //新建长度为2len的数组C int i,j; for (i = 0; i < len; i++) C[i] = A[i]; //将数组A复制到数组C的前半段中 for (j = 0; j < len; i++, j++) C[i] = B[j]; //将数组B复制到数组C的后半段中 QuickSort(C, 0, 2 * len - 1); //对数组C进行快速排序 cout << C[len - 1]; //输出中位数 }
（2）数组指针后移把数存入第三个数组（用count记录进行次数的方法并不能降低时间复杂度，省略系数后还是n的时间复杂度）
int GetMidNum(int A[], int B[], int len) { int *C = (int*)malloc(sizeof(int) * 2 * len); int i, j, k; for(i = 0, j = 0, k = 0; i < len && j < len; k++){ if (A[i] < B[j]) { //比较A[i]和B[j]，更小的存入C，并且该数组的指针向后移 C[k] = A[i]; i++; } else { C[k] = B[j]; j++; } } cout << C[len - 1]; }
（3）数组指针后移（本质上和2一样，都是控制指针后移）
int GetMidNum(int A[], int B[], int len) { int count = 0, i, j, res; while (i < len && j < len && count < len) { if (A[i] < B[j]) { i++; res = A[i]; } else { j++; res = B[j]; } count++; } cout << res; }
int GetMidNum(int A[], int B[], int len) { int i, j, k; for (k = 1, i = 0, j = 0; k < n; k++) { //一共移动n - 1次 if (A[i] < B[j]) i++; else j++; } cout << min(A[i], B[j]); //输出A和B数组中当前元素的较小值 }
6.1.3.（2013） 
（1）枚举：逐个元素判断（两层循环）
void MainNum(int A[], int n) { int i, j, count; for (i = 0; i < n; i++) { for (j = 0, count = 0; j < n; j++) { if (A[j] == A[i]) count ++; //当前A[j]等于A[i]，出现次数+1 } if (count > n / 2) { cout << A[i]; //A[i]出现次数满足主元素要求，输出A[i] return; //结束 } } cout << -1; //没有主元素，输出-1 return; }
（2）快速排序：
int Partation(int arr[], int low, int high) { 随机选定数组下标low - high之间的元素和arr[low]对调 //快排优化 int pivot = arr[low]; while (low < high) { while (low < high && arr[high] >= pivot) high--; arr[low] = arr[high]; while (low < high && arr[low] <pivot) low++; arr[high] = arr[low; } arr[low] = pivot; return low; } void QuickSort(int arr[], int low, int high) { //快速排序 if (low < high) { int pivotPos = Partation(arr, low, high); QuickSort(arr, low, pivotPos - 1); QuickSort(arr, pivotPos + 1, high); } } int MainNum(int arr[], int n) { //count标记当前元素的出现次数，current记录当前元素 int i, current = arr[0], count = 1; for (int i = 1; i < n; i++) { //遍历数组 if (arr[i] == current) count ++; //当前元素和current相同，出现次数 + 1 else { //当前元素和current不同，用当前元素替换current，并且出现次数归1 current = A[i]; count = 1; } if (count > n / 2) return current; //出现次数大于>n/2，则current为主元素 } return -1; //没有主元素，返回-1 }
（3）动态规划：空间换时间，A出现的元素范围是正整数且<n，申请一个长度为n的数组，
第一遍遍历A数组记录每个元素其值出现的次数：设A中出现i，则count[i]++
第二遍遍历count数组，找是否有元素的值 > n/2，即A中出现次数 > n/2
int GetMainNum(int A[], int n) { int *count = (int*)malloc(sizeof(int) * n); memset(count, 0 , sizeof(int) * n); //遍历数组，将当前元素的值作为下标在count中对应元素+1 for (int i = 0; i < n; i++) count[A[i]]++; //count[i]元素的值即i在A中出现的次数 for (int i = 0; i < n; i++) { if (count[i] > n / 2) return i; //i出现次数>n/2，i为主元素 } return -1; }
6.1.4.（2016）
快速排序：先对数组进行排序即满足需求（向下取整，即数组个数为奇数时，右大左小）
int Partation(int arr[], int low, int high) { 随机选择一个数组下标为low - high的元素和arr[low]交换 //快排优化 int pivot = arr[low]; while (low < high) { while (low < high && arr[high] >= pivot) high--; arr[low] = arr[high]; while (low < high && arr[low] < pivot) low++; arr[high] = arr[low]; } arr[low] = pivot; return low; } void QuickSort(int arr[], int low, int high){ if (low < high) { int pivotPos = Partation(arr, low , high); QuickSort(arr, low, pivotPos - 1); QuickSort(arr, pivotPos + 1, high); } } void Divid(int arr[], int n){ QuickSort(arr, 0, n - 1); //快速排序 for (int i = 0; i < n / 2; i++) cout << arr[i] << endl; //输出子集A1 for (int i = n / 2; i < n; i++) cout << arr[i] << endl; //输出子集A2 }
6.1.5.（2018）
（1）快速排序
int Partation(int arr[], int low,int high) { 随机选择一个数组下标为low - high之间的元素和arr[low]交换 //快排优化 int pivot = arr[low]; while (low < high) { while (low < high && arr[high] >= pivot) high--; arr[low] = arr[high]; while (low < high && arr[low] < pivot) low--; arr[high] = arr[low]; } arr[low] = pivot; return low; } void QuickSort(int arr[], int low, int high) { if (low < high) { int pivotPos = Partation(arr, low, high); QuickSort(arr, low, pivotPos - 1); QuickSort(arr, pivotPos + 1, high); } } int GetNum(int arr[], int n) { QuickSort(arr, 0, n - 1); //将数组排序成有序 int i, j; while (arr[i] <= 0 && i < n) i++; if (i == n) return 1; //数组中的没有正数 if (arr[i] != 1) return 1; //此时arr[i]为数组中最小正整数 //如果不是1，则1是未出现的最小正整数 else { //arr[i]为1，找到第一个正数间断点 j = i + 1; while (j < n && arr[j] != arr[j - 1] && arr[j] != arr[j - 1] + 1); return arr[j - 1] + 1; //返回上一个元素+ 1的值 } }
（2）空间换时间
int MinNum(int arr[], int n) { int *count = (int*)malloc(sizeof(int) * (n + 1)); memset(count, 0, sizeof(int) * (n + 1)); int i; //遍历数组，当前元素大于0，则在count数组以该元素为数组下标的元素自增1 for (i = 0; i < n; i++) if (arr[i] > 0) count[arr[i]]++; //count数组元素的值即该下标在arr数组中出现的次数，返回第一个为0的下标 for (i = 1; i < n + 1; i++) if (count[i] == 0) return i; }
6.1.6.（2020）
int GetDis(int a, int b){ int c = a - b; if (c >= 0) return c; else return -c; } int MinDis(int A[], int B[], int C[], int lenA, int lenB, int lenC){ int i, j, k, temp; int min = MAX_INT; //将min初始化为INT类型的最大值 for (i = 0; i < lenA; i++){ for (j = 0; j < lenB; j++){ for (k = 0; k < lenC; k++){ //计算三个数组当前元素的距离 temp = GetDis(A[i], B[j]) + GetDis(A[i], C[k]) + GetDis(B[j], C[k]); //更新min if (temp < min) min = temp; } } } return min; }
6.2.链表
6.2.1.（2009）
（1）前后指针
int GetK(LNode *L, int k){ LNode *p = L, *q = L; for (int i = 1; i < k; i++) p = p->link; //p向前移动k - 1个结点 while(p->link) { //p和q同步移动，p移动至链表最后一个结点时，q就是倒数第k个结点 p = p->link; q = q->link; } return q->data; //返回q的data }
（2）用数组保存每个结点的值
int GetK(LNode *L, int k){ int len = 0; LNode *p = L; while (p) { //遍历链表得到链表长度 p = p->link; len++; } int *arr = (int*)malloc(sizeof(int) * len); //申请和链表长度相同的数组 int i = 0; p = L; while (p) { //遍历链表，保存每个结点的值到数组中 arr[i++] = p->data; p = p->link; } cout << arr[n - k]; //输出倒数第k个结点 }
（3）遍历数组两次，第一次得到数组的长度，第二次移动到倒数第k个
int ans(LNode *L, int k){ int len = 0; LNode *p = L; while (p) { //第一遍循环得到链表长度 p = p->next; len++; } p = L; //p重新指向头结点 count = n - k + 1; while (count > 0) p = p->next; cout << p->data; }
