标签搜索

目 录CONTENT

文章目录

腾讯2020校园招聘----逆序对.md

小小城
2022-05-02 / 0 评论 / 0 点赞 / 4 阅读 / 4,876 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

-逆序对.md
date: 2021-08-22 12:10:10.053
updated: 2021-08-22 12:10:10.053
url: /2021/08/22/腾讯2020校园招聘----逆序对md
categories:
tags:

腾讯2020校园招聘----逆序对

@[toc]

一、题目描述

在这里插入图片描述
在这里插入图片描述

二、题目分析

首先,我们看到要求逆序对,我们做出这道题的前提是会求逆序对,所以先分析怎么求逆序对;

答案:《剑指offer》36题

代码:

class Solution {
public:
    
    //简单的归并排序
    //最好在过程当中%一下,否则不过
    long long Merge(vector<int>& data,int begin,int end,vector<int>& temp)
    {
        if(begin == end)
        {
            return 0;
        }
        
        long long count = 0;
        
        int mid = (begin + end) >> 1;
        //把数组分为更小的左右两部分
        int left = Merge(data,begin,mid,temp)% 1000000007;
        int right = Merge(data,mid + 1,end,temp)% 1000000007;
        
        //进行标记
        int begin1 = begin;
        int end1 = mid;
        int begin2 = mid + 1;
        int end2 = end;
        
        int index = end;
        //每一块比较大小
        while(begin1 <= end1 && begin2 <= end2)
        {
            //如果前面区间的数字比后面区间的数字大,就构成逆序对
            //逆序对的个数为后面区间的begin到end(end是在动态改变的)位置处的元素的个数
            //原因是归并的特性,是先把小区间有序,在合并大区间有序,所以两个区间内部肯定是有序的
            //如果前面区间的某个数字m比后面区间的某个数字n大,那么m就比后面区间的某个
            //数字m之前的数都大
            if(data[end1] > data[end2])
            {
                count = (count + end2 - begin2 + 1)% 1000000007;
                temp[index] = data[end1];
                end1--;
                index--;
            }
            else 
            {
                temp[index] = data[end2];
                end2--;
                index--;
            }
        }
        while(end1 >= begin1)
        {
            temp[index--] = data[end1--];
        }
        while(end2 >= begin2)
        {
            temp[index--] = data[end2--];
        }
        //拷贝
        for(int i =  begin;i <= end ;i++)
        {
            data[i] = temp[i]; 
        }
        
        //左边区间的逆序对的个数 + 由边区间的逆序对的个数 + 合并两个区间的逆序对的个数
        return (left + right + count)% 1000000007;
        
    }
    int InversePairs(vector<int> data) {
       if(data.empty())
       {
           return 0;
       }
        vector<int> temp(data.size());
       
        return Merge(data,0,data.size() - 1,temp) ;
    }
};

方法一:暴力求解(超时)

你会求逆序对,剩下就是反转了,直接看代码:

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
 
long long  Merge(vector<int> info,int begin,int end,vector<int> temp)
{
    if(begin == end)
    {
        return 0;
    }
    long long count = 0;
     
    int mid = (begin + end) >> 1;
    long long left = Merge(info,begin,mid,temp);
    long long right = Merge(info,mid + 1,end,temp);
     
    int begin1 = begin;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = end;
    int index = end;
     
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(info[end1] > info[end2])
        {
            count = count + end2 - begin2 + 1;
            temp[index--] = info[end1--];
        }
        else
        {
            temp[index--] = info[end2--];
        }
    }
    while(end1 >= begin1)
    {
        temp[index--] = info[end1--];
    }
    while(end2 >= begin2)
    {
        temp[index--] = info[end2--];
    }
    //拷贝
    for(int i =  begin;i <= end ;i++)
    {
        info[i] = temp[i];
    }
         
        //左边区间的逆序对的个数 + 由边区间的逆序对的个数 + 合并两个区间的逆序对的个数
    return (left + right + count);
}
 
void InversePairs(vector<int> info)
{
    vector<int> temp(info.size());
     
    cout<<Merge(info,0,info.size() - 1,temp)<<endl;
}
 
void Reverse(vector<int>& info,int num)
{
    int count = info.size() / num;
    for(int i = 0;i < count;i++)
    {
        reverse((info.begin() + i * num),info.begin() + ((i + 1) * num));
         
    }
    InversePairs(info);
}
 
void GetReverseCount(vector<int>& info,vector<int>& ans)
{
    for(auto e : ans)
    {
        int num = pow(2,e);
        Reverse(info,num);
    }
}
 
int main()
{
    int n;
    cin>>n;
    vector<int> v(pow(2,n));
    for(int i = 0;i < pow(2,n);i++)
    {
        cin>>v[i];
    }
    int num;
    cin>>num;
    vector<int> ans(num);
    for(int i = 0;i < num;i++)
    {
        cin>>ans[i];
    }
    GetReverseCount(v,ans);
     
    return 0;
}

方法二:优化

每次翻转,然后利用归并排序求解逆序对,复杂度太高,只能通过50%的数据。显然每次都要归并排序成本太高,那么可不可只使用一次归并排序哪?

  •  可以发现,逆序对翻转后,变成顺序对,如1 2,翻转变成2 1
  •  因此我们需要 记录不同长度的逆序对和顺序对的数量,当翻转时,仅需交换小于等于该翻转长度的逆序对和顺序对(因为大于翻转长度的逆序对不会收到影响),将所有的逆序对加起来即可得到结果。
  •  举个例子,如 2 1 4 3,长度为2 ^ 1的逆序对数量为2(2 1一对,4 3一对),长度为2 ^ 2的逆序对数量为0(2 1 4 3中2 1 和4 3不构成逆序对,不要重复计算)。之后便可以只交换逆序对和顺序对数量,求逆序对的和即可
  •  顺序对怎么计算,可以考虑用 总数-逆序对-相等的对
#include <vector>
#include <iostream>
#include <math.h>
using namespace std;
void merge(vector<long long int>&nums, long long int lbegin, long long int lend,long long int rbegin,long long int rend,long long int index,vector<long long int>&cnt) {
    long long int p1 = lbegin, p2 = rbegin;
    vector<long long int> tmp(rend - lbegin + 1);
    long long int i = 0;
    long long int pairsCnt = 0;
    while (p1 <= lend && p2 <= rend) {
        if (nums[p1] <= nums[p2]) {
            tmp[i++] = nums[p1++];
        }
        else if(nums[p1]>nums[p2]){
            pairsCnt += (lend - p1 + 1);
            tmp[i++] = nums[p2++];
        }
    }
    while (p1 <= lend) {
        tmp[i++] = nums[p1++];
    }
    while (p2 <= rend) {
        tmp[i++] = nums[p2++];
    }
    for (int i = 0; i < tmp.size(); i++) {
        nums[lbegin++] = tmp[i];
    }
    cnt[index] += pairsCnt;
}
void mergeSort(vector<long long int>& nums, long long int begin, long long int end, long long int index,vector<long long int>& cnt) {
    if (begin == end)
        return;
    long long int mid = (end - begin) / 2 + begin;
    mergeSort(nums, begin, mid,index-1,cnt);
    mergeSort(nums, mid + 1, end,index-1,cnt);
    merge(nums, begin, mid, mid + 1, end,index,cnt);
}
int main() {
    ios::sync_with_stdio(false);
    long long int n;
    cin >> n;
    long long int cnt = pow(2, n);
    vector<long long int> nums;
    while (cnt--) {
        long long int tmp;
        cin >> tmp;
        nums.push_back(tmp);
    }
    vector<long long int> order(n+1,0);//保存不同长度的顺序对个数
    vector<long long int> reOrder(n+1,0);//保存不同长度的逆序对个数
    vector<long long int> reverse_nums(nums.rbegin(), nums.rend());
    mergeSort(nums, 0, nums.size() - 1,n,reOrder);
    mergeSort(reverse_nums, 0, reverse_nums.size() - 1, n,order);
    long long int m;
    cin >> m;
    while (m--) {
        long long int q;
        cin >> q;
        long long int cnt = 0;
        for (long long int i = 1; i <= q; i++) {
            swap(order[i], reOrder[i]);//每次反转后,需要交换q范围内顺序对和逆序对的数量
        }
        for (long long int i = 1; i <= n; i++) {
            cnt += reOrder[i];
        }
        cout << cnt << endl;
    }
    system("pause");
    return 0;
}

0

评论区