题解 | #数组元素交换#

> 思路：用临时数组b来存储a,并对b进行快速排序（从大到小排序）,从而找到第n大的数字和第m大的数。然后遍历数组a,对第n大的数字和第m大的数交换位置。

class Solution {
public:

    vector<int> sovle(vector<int>& a, int n, int m) {
        vector<int> b=a;
        sort(b.begin(),b.end(),greater<int>());//从大到小排序
        int num=a.size();
        for(int i=0;i<num;i++){
            if(a[i]==b[n-1])//如果是第n大的数字，则变为第m大的数
                a[i]=b[m-1];
            else if(a[i]==b[m-1])//如果是第m大的数字，则变为第n大的数
                a[i]=b[n-1];
        }
        return a;
    }
};

> 时间复杂度：

> 空间复杂度：

思路：map使用红黑树实现，值是有序的，数组a没有重复元素，所以用map实现值到下标的映射。因为值是有序的，所以逆向遍历可以找到

第n大的数字和第m大的数，再交换第n大和第m大的值。

class Solution {
public:

    vector<int> sovle(vector<int>& a, int n, int m) {
        map<int,int> mp;//值到下标的映射
        int num=a.size();
        for(int i=0;i<num;i++){//初始化map
            mp[a[i]]=i;
        }
        int i=1,x,y;
        for(auto it=mp.rbegin();it!=mp.rend();it++){//反向遍历
            if(i==n)//寻找第n大的下标
                x=it->second;
            else if(i==m)//寻找第m大的下标
                y=it->second;
            i++;
        }
        swap(a[x],a[y]);//交换第n大和第m大的值
        return a;
    }
};

> 时间复杂度：

> 空间复杂度：