不要使用蛮力算法
答案
暴力解法, 会超时
- long long a(vector<string>& v, int pos1, int pos2) {
- long long w = 0;
- for (int i = pos1; i <= pos2; ++i) {
- for (int j = i + 1; j <= pos2; ++j) {
- if (v[i]> v[j])
- ++w;
- }
- }
- return w;
- }
- bf
归并排序的思想, 只需要在归并排序的基础之上加上一个统计量, 和一行代码, 但是下面的做法会超出内存限制
- void merge(vector <string> &v, int pos1, int mid, int pos2, long long & nums) {
- // 从 0 开始的数组, 如果两个位置分别为 p1 和 p2, 其中 p1<p2, 则 p1 到 p2 距离的元素有 p2-p1+1 个
- vector <string> n1(v.begin() + pos1, v.begin() + mid + 1);
- vector <string> n2(v.begin() + mid + 1, v.begin() + pos2 + 1);
- n1.emplace_back("zzzzzzzzzzzzzzzzzzzz");
- n2.emplace_back("zzzzzzzzzzzzzzzzzzzz");
- int n1_pos = 0;
- int n2_pos = 0;
- for (int i = pos1; i <= pos2; ++i) {
- if (n1[n1_pos] <= n2[n2_pos]) {
- v[i] = n1[n1_pos]; ++n1_pos;
- } else {
- // 在这加上统计量
- nums += n1.size() - n1_pos - 1;
- v[i] = n2[n2_pos]; ++n2_pos;
- }
- }
- }
- void mergesort(vector <string> &v, int pos1, int pos2, long long & nums) {
- if (pos1 <pos2) {
- int mid = (pos1 + pos2) / 2;
- mergesort(v, pos1, mid, nums);
- mergesort(v, mid + 1, pos2, nums);
- merge(v, pos1, mid, pos2, nums);
- }
- }
- // 这是测试用例
- int main() {
- int nums = 0;
- cin>> nums;
- string temp;
- vector <string> v(nums, "");
- for (int i = 0; i <nums; ++i) {
- cin>> temp;
- v[i] = temp;
- }
- vector <string> v = {
- "aaaaaaaaaa",
- "cccccccccc",
- "bbbbbbbbbb"
- };
- long long result = 0;
- mergesort(v, 0, v.size() - 1, result);
- cout <<"wo yi yue du guan yu chao xi de shuo ming" << endl;
- cout << result << endl;
- //system("pause");
- return 0;
- }
归并解法
经大佬提醒, 不在递归时分配 vector, 而是在开始递归之前申请一个 help 的 vector 用来帮助归并排序, 这样可以减小内存使用, 但是上面使用哨兵的方法就不能用了, 代码稍微复杂了一些, 但任然是归并排序加上一行统计代码
- void merge(vector<string>& v, int pos1, int mid, int pos2, long long& nums, vector<string>& help) {
- // 从 0 开始的数组, 如果两个位置分别为 p1 和 p2, 其中 p1<p2, 则 p1 到 p2 距离的元素有 p2-p1+1 个
- for (int i = pos1; i <= pos2; ++i)
- help[i] = v[i];
- int n1_pos = pos1;
- int n2_pos = mid+1;
- for (int i = pos1; i <= pos2;++i) {
- // 当一个数组已经遍历完成时
- if (n1_pos == mid + 1) {
- while (n2_pos != pos2 + 1) {
- v[i++] = help[n2_pos++];
- }
- break;
- }
- if (n2_pos == pos2 + 1) {
- while (n1_pos != mid + 1) {
- v[i++] = help[n1_pos++];
- }
- break;
- }
- // 其他情况
- if (help[n1_pos] <= help[n2_pos]) {
- v[i] = help[n1_pos];
- ++n1_pos;
- }else{
- // 在这加上统计量
- nums += mid-n1_pos+1;
- v[i] = help[n2_pos];
- ++n2_pos;
- }
- }
- }
- void mergesort(vector<string>& v, int pos1, int pos2, long long& nums,vector<string>& help) {
- if (pos1 <pos2) {
- int mid = (pos1 + pos2) / 2;
- mergesort(v,pos1,mid,nums,help);
- mergesort(v,mid+1,pos2,nums,help);
- merge(v,pos1,mid,pos2,nums,help);
- }
- }
- // 这是测试用例
- int main()
- {
- int nums = 0;
- cin>> nums;
- string temp;
- vector<string> v(nums,"");
- for (int i = 0; i <nums; ++i) {
- cin>> temp;
- v[i] = temp;
- }
- //vector<string> v = { "4","3","2","1" };
- vector<string> help(v.size()," ");
- long long result = 0;
- mergesort(v, 0, v.size() - 1, result,help);
- cout << "wo yi yue du guan yu chao xi de shuo ming" << endl;
- cout << result << endl;
- system("pause");
- return 0;
- }
归并排序内存优化
来源: http://www.bubuko.com/infodetail-2536894.html