题解 | #数组元素交换#

数组元素交换

http://www.nowcoder.com/practice/031c57a3f8f4423597eee57e54065a9b

题意整理：

题目给出个没有重复元素的数组a，需要要将数组内第n大的数字和第m大的数交换位置，返回交换后的数组

方法一：排序+替换

核心思想：

可以将原数组复制一份，将复制得到的数组进行排序(从大到小)，然后取出第n大和第m大的数的数值，再在原数组中进行查找并替换即可。因为题目保证的数组中没有重复元素，所以可以保证算法的正确性

核心代码：

class Solution {
public:
    vector<int> sovle(vector<int>& a, int n, int m) {
        vector<int>res(a);//用于排序
        sort(res.begin(), res.end(), greater<int>());
        //取得排序后对应的需要交互的元素的值
        int r1 = res[n - 1];
        int r2 = res[m - 1];
        for(int& i : a) {
            //查找对应元素进行交换
            if(i == r1) {
                i = r2;
            } else if(i == r2) {
                i = r1;
            }
        }
        return a;
    }
};

复杂度分析：

时间复杂度： $O(nlogn)$ 。对数组排序的开销为 $O(nlogn)$ ，替换过程中的开销为 $O(n)$ ，故总开销为 $O(nlogn)$
空间复杂度： $O(n)$ ,既用于排序的临时数组的开销

方法二：部分排序(快排思想)+替换

核心思想：

方法一是直接对整个数组排序，开销为 $O(nlogn)$ ，而实际上只是需要获取位置n以及位置m上的数值即可，故可以利用快排的思想，不对整个数组排序，而只是对数组的一部分排序。
快排算法：快速排序是对冒泡排序的优化，它的思想就是每次选定一个枢纽值，然后对区间进行一次遍历，使得小于枢纽值的数位于其左侧，大于枢纽值的数位于其右侧，再对其两次元素进行递归。
而在这里，可以对递归环节进行优化，既然题目只需要获取一个排序后的点的值，所以在确保一侧元素都对另一侧元素存在有序性（左侧都小于右侧，右侧都大于左侧）时，只需要对一侧进行递归，既如果所需值在左侧，既递归左侧，所需值在右侧，既只递归右侧。
注意的点：快速排序存在最坏情况，此时退化为冒泡排序，为防止其退化，枢纽值的选取不能够固定，一般有两种方法，既随机取枢纽值，以及三值取中法，STL中的sort采用的就是三值取中法，此处也采用三值取中法。
三值取中法首先对数组左值，右值和中间值进行调整，保证左，中，右三值的顺序性，然后选择中值作为枢纽，同时将枢纽归位到右值左侧，然后从左值右侧和枢纽值左侧开始处理，处理完毕后将枢纽值归为即可
下图简单的说明了三值取中法的第一轮排序过程

原数组 3 5 1 2 7 4 8
三值取中调整后 2 5 1 3 7 4 8 (确保左值，中值，右值的顺序性)
枢纽值(3)移动 2 5 1 4 7 3 8 (4与3互换位置)
处理中间(5-7) 2 1 5 4 7 3 8
枢纽值归位 2 1 3 4 7 5 8
图片说明

核心代码：

class Solution {
public:
    int medium(vector<int>& nums, int left, int right) { 
        //三值取中
        int mid = (left + right) / 2;
        if(nums[left] > nums[right]) swap(nums[left], nums[right]);
        if(nums[left] > nums[mid]) swap(nums[left], nums[mid]);
        if(nums[mid] > nums[right]) swap(nums[mid], nums[right]);
        swap(nums[mid], nums[right - 1]);//将枢纽放到末尾
        return nums[right - 1];
    }

    void quickSort(vector<int>& nums, int left, int right, int k) {
        //单侧快排
        if(left >= right) return;
        int p = medium(nums, left, right);
        int i = left, j = right - 1;
        while(i < j) {
            while(nums[++i] < p);
            while(nums[--j] > p);
            if(i < j) swap(nums[i], nums[j]);
        }
        swap(nums[i], nums[right - 1]);//枢纽归位
        //只递归需要的一侧
        if(i < k) quickSort(nums, i + 1, right, k);
        else if(i > k) quickSort(nums, left, i - 1, k);
    }

    int help(vector<int>& nums, int k) {
        quickSort(nums, 0, nums.size() - 1, nums.size() - k);
        return nums[nums.size() - k];
    }

    vector<int> sovle(vector<int>& a, int n, int m) {
        vector<int> res(a);
        //取得排序后对应的需要交互的元素的值
        int r1 = help(res, n);
        int r2 = help(res, m);
        for(int& i : a) {
            //查找对应元素进行交换
            if(i == r1) {
                i = r2;
            } else if(i == r2) {
                i = r1;
            }
        }
        return a;
    }
};