圈圈小站

quanquan's blog

0%

leetcode刷题笔记——排序

发表于 分类于

leetcode刷题笔记——排序类。

1.调整数组顺序使奇数位于偶数前面

  • 不改变原有的相对关系。

【法一】空间换时间，新开辟一个数组。

【法二】采用冒泡排序思想，奇数上浮到偶数左边。

1
2
3
4
5
6
7
8
9
void reOrderArray(vector<int> &array) {
        int len = array.size();
        for (int i=0; i<len; i++){
            for (int j=len-1; j>i; j--){
                if (array[j]%2==1&&array[j-1]%2==0)
                    swap(array[j],array[j-1]);
            }
        }
    }

【法三】双指针，先找到最前的偶数i，在向后找第一个奇数j，其间每一个数向后移，j移到i的位置上。

  • 可以改变相对关系

【法一】首尾指针

奇偶交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> exchange(vector<int>& nums) {
        int len = nums.size();
        int i=0,j=len-1;
        while(i<j){
            while ((nums[i]&1)==1&&i<j){
                i++;
            }
            while ((nums[j]&1)==0&&i<j){
                j--;
            }
            if (i<j)
                swap(nums[i],nums[j]);
        }
        return nums;
    }

【法二】快慢指针

搜索每个奇数放到该去的位置。

1
2
3
4
5
6
7
8
9
10
11
vector<int> exchange(vector<int>& nums) {
        int len = nums.size();
        int i=0,j=0;
        for (; j<len; j++){
            if (nums[j]&1){
                swap(nums[i],nums[j]);
                i++;
            }
        }
        return nums;
    }

2.把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组 {3，32，321}，则打印出这三个数字能排成的最小数字为 321323。

实际上是字符串排序问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool static cmp(string a, string b){  //函数指针
    return a+b<b+a;
}
string PrintMinNumber(vector<int> numbers) {
    vector<string> str;
    for (int val:numbers){
        str.push_back(to_string(val));
    }
    sort(str.begin(),str.end(),cmp);
    string ans="";
    for (string s:str){
        ans+=s;
    }
    return ans;
}

to_string c++11：数字转字符串

3.求逆序对

【法一】归并排序思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int mergeSort(vector<int>& array,vector<int>& copyArray, int left, int right){
        int ans=0;
        if (right<=left) return 0;
        int mid = (right+left)/2;
        ans = mergeSort(array,copyArray,left,mid)+mergeSort(array,copyArray,mid+1,right);
        int i=left, j=mid+1, k=0;
        while (i<=mid||j<=right){
            if (i>mid){
                copyArray[k] = array[j];
                j++;
            }
            else if (j>right){
                copyArray[k] = array[i];
                i++;
            }
            else if (array[i]>array[j]){
                copyArray[k] = array[j];
                ans+=j-left-k;
                j++;
            }
            else{
                copyArray[k] = array[i];
                i++;
            }
            k++;
        }
        for (int i=left; i<=right; i++){
            array[i] = copyArray[i-left];
        }
        return ans;
    }
    int reversePairs(vector<int>& nums) {
        vector<int> copyArray(nums);
        return mergeSort(nums,copyArray,0,nums.size()-1);
    }
};

【法二】树状数组

。。。以后再补充