为了解决这道题,我们选用了c++中的vector作为数据结构,因为vector的增加,删除操作较为简单。
要解决该问题我们需要几个相关函数作为支持。
vector<int> find_k_near_mid(vector<int>& list, int k) //主要的求解函数,返回值为一个vector数组。 int select(vector<int> list,int tt) //求解输入的list中的有序时的第tt个数(从0开始计算)的值 sort(vector<int> &list) //插入排序算法 int partition(vector<int> &list, int x) //以x为主元对list进行划分 int partition1(vector<vector<int>> &list, int x) //功能与上一个函数一致,只是输入参数不同
select()函数:该函数可以返回按序排列的第tt个数的值,我们也可以用它来求解中位数。
它是通过划分数组,之后递归调用的方式执行,时间复杂度为O(n),书上有更为具体的描述.
int select(vector<int> list,int tt){ if(list.size() == 1){ return list[0]; } vector<vector<int>> div; for(int i = 0; i <= list.size()/5; i++){ vector<int> temp; for(int j = 0; j < 5; j++){ if(i * 5 + j == list.size()){ break; } temp.push_back(list[i * 5 + j]); } if(temp.size() != 0){ sort(temp); //用冒泡排序的方法对这5个数排序 div.push_back(temp); } } //建立二维vector,5个一组存储list的值 vector<int> mid_temp(div.size()); for(int i = 0; i < div.size(); i++){ mid_temp[i] = div[i][(div[i].size()-1)/2]; } //建立存储中位数的vector int mid_mid_temp; mid_mid_temp = select(mid_temp, (mid_temp.size()-1)/2); //求中位数数组的中位数 int position_mid_mid_temp = partition(list, mid_mid_temp); //求出中位数数组的中位数在list中的位置,并对中位数数组做划分,k之前是小于mid_mid_temp的数,之后是大于该值的数。 int k = position_mid_mid_temp; vector<int> low(list.begin(), list.begin() + k); vector<int> high(list.begin() + k + 1, list.end()); //用k对数组进行划分 if(tt == k){ return mid_mid_temp; } else if(tt < k){ return select(low, tt); } else { return select(high, tt - k - 1); } }
sort()函数:插入排序,不需要过多介绍。
void sort(vector<int> &list){ int temp; for(int i = 0; i < list.size(); i++){ for(int j = i; j < list.size(); j++){ if(list[i] > list[j]){ temp = list[i]; list[i] = list[j]; list[j] = temp; } } } }
partition()函数:以传入的x为主元,对数组进行划分,并且返回x在划分好的数组中的位置。
int partition(vector<int> &list, int x) { int i = -1,temp; for(int j = 0; j < list.size(); j++){ if(list[j] <= x){ i++; temp = list[j]; list[j] = list[i]; list[i] = temp; } } return i; } int partition1(vector<vector<int>> &list, int x) { int i = -1; vector<int> temp; for(int j = 0; j < list.size(); j++){ if(list[j][1] <= x){ i++; temp = list[j]; list[j] = list[i]; list[i] = temp; } } return i; }
find_k_near_mid()函数:
首先,调用select()函数求出中值,之后建立一个二维vector,每一维有两个参数,第一个为list中的数减去mid的符号,第二个为这个值的绝对值。这个绝对值也存储在一个名为temp的容器中。
我们调用select()函数,求出temp中有序排列时的第k(从1开始计数)个值。之后通过这个值调用partition1()函数对二维容器进行划分。
在数组划分好后,我们用前k个值的绝对值乘以符号位加上中位数即为需要的值。
vector<int> find_k_near_mid(vector<int>& list, int k) { int mid = select(list, (list.size()-1)/2); vector<vector<int>> b(list.size()); vector<int> temp; int temp_num; for(int i=0; i<list.size(); i++){ temp_num = list[i] - mid; if(temp_num < 0){ b[i].push_back(-1); b[i].push_back(abs(temp_num)); temp.push_back(abs(temp_num)); } else{ b[i].push_back(1); b[i].push_back(temp_num); temp.push_back(temp_num); } } int x = select(temp, k-1); partition1(b, x); vector<int> result; for(int i=0; i<k; i++){ result.push_back(b[i][0]*b[i][1] + mid); } return result; }
完整代码(含测试代码):
#include<vector> #include <iostream> #include <stdlib.h> using namespace std; class Solution { public: vector<int> find_k_near_mid(vector<int>& list, int k) { int mid = select(list, (list.size()-1)/2); vector<vector<int>> b(list.size()); vector<int> temp; int temp_num; for(int i=0; i<list.size(); i++){ temp_num = list[i] - mid; if(temp_num < 0){ b[i].push_back(-1); b[i].push_back(abs(temp_num)); temp.push_back(abs(temp_num)); } else{ b[i].push_back(1); b[i].push_back(temp_num); temp.push_back(temp_num); } } int x = select(temp, k-1); partition1(b, x); vector<int> result; for(int i=0; i<k; i++){ result.push_back(b[i][0]*b[i][1] + mid); } return result; } int select(vector<int> list,int tt){ if(list.size() == 1){ return list[0]; } vector<vector<int>> div; for(int i = 0; i <= list.size()/5; i++){ vector<int> temp; for(int j = 0; j < 5; j++){ if(i * 5 + j == list.size()){ break; } temp.push_back(list[i * 5 + j]); } if(temp.size() != 0){ sort(temp); div.push_back(temp); } } vector<int> mid_temp(div.size()); for(int i = 0; i < div.size(); i++){ mid_temp[i] = div[i][(div[i].size()-1)/2]; } int mid_mid_temp; mid_mid_temp = select(mid_temp, (mid_temp.size()-1)/2);//zhuyi tt dezhi int position_mid_mid_temp = partition(list, mid_mid_temp); int k = position_mid_mid_temp; vector<int> low(list.begin(), list.begin() + k); vector<int> high(list.begin() + k + 1, list.end()); if(tt == k){ return mid_mid_temp; } else if(tt < k){ return select(low, tt); } else { return select(high, tt - k - 1); } } void sort(vector<int> &list){ int temp; for(int i = 0; i < list.size(); i++){ for(int j = i; j < list.size(); j++){ if(list[i] > list[j]){ temp = list[i]; list[i] = list[j]; list[j] = temp; } } } } int partition(vector<int> &list, int x) { int i = -1,temp; for(int j = 0; j < list.size(); j++){ if(list[j] <= x){ i++; temp = list[j]; list[j] = list[i]; list[i] = temp; } } return i; } int partition1(vector<vector<int>> &list, int x) { int i = -1; vector<int> temp; for(int j = 0; j < list.size(); j++){ if(list[j][1] <= x){ i++; temp = list[j]; list[j] = list[i]; list[i] = temp; } } return i; } }; int main(){ Solution A; int a[9]={1,2,3,4,5,6,7,8,9}; vector<int> num1(a,a+9); int i = A.select(num1,4); cout << i << endl; vector<int> a1; a1=A.find_k_near_mid(num1,3); }
新人博主,点个赞再走吧。