题意

交换无重复元素的数组中第$mm$m大和第$nn$n大的数字，返回交换后的新数组

方法

for套for

控制上限每次找小于上限的最大值，这样找了n次，就是第n大的值

我们把最大值最小值用long long来表示保证超过int的范围

以7 3 2 8 4 为例, 若$n=4n=4$n=4

所以第$44$4大的是$33$3

代码

class Solution {
public:
    int findMaxN(vector<int> & a,int n){
        int pos = -1;
        long long val = 0x3f3f3f3f3f; // 保证大于int
        // 每次寻找小于val的最大的，以此寻找n次 就是第n大的
        while(n--){
            long long v = -0x3f3f3f3f3f; // 保证小于int
            long long idx = 0;
            for(int i = 0;i<a.size();i++){
                if(a[i] >= val)continue; // 忽略大于等于的部分
                if(a[i] > v){
                    v=a[i];
                    idx = i;
                }
            }
            // 更新该轮搜索的结果
            pos = idx;
            val = v;
        }
        return pos;
    }
    /**
     * 
     * @param a int整型vector 原始数组a
     * @param n int整型 第n大
     * @param m int整型 第m大
     * @return int整型vector
     */
    vector<int> sovle(vector<int>& a, int n, int m) {
        vector<int> ans = a;
        swap(ans[findMaxN(a,n)],ans[findMaxN(a,m)]);
        return ans;
    }
};

复杂度分析

时间复杂度: 我们遍历n次数组寻找第n大的数，时间复杂度为$O(n\cdot a.size(\left)\right)O(n\; \backslash cdot\; a.size())$O(n⋅a.size())，交换元素是常数时间，复制数组$O\left(a.size\right(\left)\right)O(a.size())$O(a.size())，所以总时间复杂度为$\left(O\right((n+m)\cdot a.size\left(\right)\left)\right)(O((n+m)\; \backslash cdot\; a.size()))$(O((n+m)⋅a.size())) ,好在题目的数据范围的确很小能够AC

空间复杂度: 我们储存内容只有一个结果数组，和传入的a是一致的，所以空间复杂度为$O\left(n\right)O(n)$O(n)

制作pair并排序

我们的任务，找到那两个数是第$nn$n大和第$mm$m大的，找到这两个数的位置并交换。

C++默认的sort从小到大，我们把值取负并和下标做成一个pair,让c++自己去排序，这样我们就能让原始值从大到小，并且知道它的下标了

所以步骤变成

1. 制作pair<-值,下标>的vector
2. sort排序
3. swap对应未知的值
4. 返回 交换后的vector

以7 3 2 8 4 为例

从小到大排序

这样，我们对于原始值来说是从大到小8,7,4,3,2, 对于要去第$nn$n大的，去对应$n-1n-1$n−1下标就能拿到原始的下标。从而可以对a数组进行交换

代码

class Solution {
public:
    /**
     * 
     * @param a int整型vector 原始数组a
     * @param n int整型 第n大
     * @param m int整型 第m大
     * @return int整型vector
     */
    vector<int> sovle(vector<int>& a, int n, int m) {
        vector<pair<int,int> > b;
        for(int i = 0;i<a.size();i++){
            b.push_back({-a[i],i});
        } 
        sort(b.begin(),b.end());
        vector<int> ans = a;
        swap(ans[b[n-1].second],ans[b[m-1].second]);
        return ans;
    }
};

复杂度分析

时间复杂度: 建立 排序vector和结果vector,$O\left(n\right)O(n)$O(n),排序过程期望是$O\left(nlog\right(n\left)\right)O(n\; log(n))$O(nlog(n)),总时间复杂度$O(n\cdot log(n\left)\right)O(n\backslash cdot\; log(n))$O(n⋅log(n))

空间复杂度: 我们储存内容主要是两个vector,内容数量和传入的a是一致的，所以空间复杂度为$O\left(n\right)O(n)$O(n)

知识点

1. 大多数情况你需要建立一个不是很极限大小的数组时会耗费$O\left(n\right)O(n)$O(n)时间，对他排序是$O\left(nlog\right(n\left)\right)O(n\; log(n))$O(nlog(n)), 一般来说没有卡常数的题目只要$O\left(n\right)O(n)$O(n)能过，一般$O\left(nlog\right(n\left)\right)O(nlog(n))$O(nlog(n))也是同样能过的，在一些更复杂的题目里，甚至题目帮你都把续排好了。
2. 使用pair和tuple能省去一些结构体的实现和构建，并能使用c++默认提供的排序，二分查找等功能，而如果自己的结构体你可能需要提供比较函数的实现，在一些支持C++更高版本的语法的地方，使用pair,tuple能写出十分简洁的代码。比如从大到小排序，你也可以提供比较函数，或者用C++提供的greater<>(), 但通过加个符号，可以简洁的实现顺序的颠倒。