题解 | #数组元素交换#
数组元素交换
http://www.nowcoder.com/practice/031c57a3f8f4423597eee57e54065a9b
**题意：
有一个没有重复元素的数组a，想要将数组内第n大的数字和第m大的数交换位置。(数组a没有重复元素)**
**方法一：
快排法**
> 思路：用临时数组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;
}
}; > 时间复杂度：%2C%E5%BF%AB%E6%8E%92%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6O(n*logn))
> 空间复杂度：%2Cn%E6%98%AF%E6%95%B0%E7%BB%84%E9%95%BF%E5%BA%A6)
map查找法**
思路：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;
}
}; > 时间复杂度：%2Cmap%E8%87%AA%E5%8A%A8%E6%8E%92%E5%BA%8F%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E6%98%AFO(n*logn))
> 空间复杂度：
查看5道真题和解析