Skip to content

Latest commit

 

History

History
373 lines (318 loc) · 10.3 KB

基础02.md

File metadata and controls

373 lines (318 loc) · 10.3 KB
Raw

2.认识O(NlogN)的排序

MySort.cpp

思维导图

2.1 递归

1. 使用递归求数组的最大值

int process(const vector<int>& arr, int L, int R){
    if(L == R)  //base case
        return arr[L];
    int mid = L + ((R - L) >> 1);   // 防止溢出
    int leftMax = process(arr, L, mid);
    int rightMax = process(arr, mid+1, R);
    return max(leftMax, rightMax);
}

2. Master公式

子问题的规模相同

  • 笔记

2.2 归并排序

将一个大的无序数组有序，可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组

✅tested

vector<int> mergeSort(vector<int>& nums) {
    process(nums, 0, nums.size() - 1);
    return nums;
}
void process(vector<int>& nums, int L, int R){
    if(L == R){
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(nums, L, mid);
    process(nums, mid + 1, R);
    merge(nums, L, mid, R);
}
void merge(vector<int>& nums, int L, int M, int R){
    vector<int> help;   //！额外空间复杂度
    int p1 = L;
    int p2 = M + 1;
    while(p1 <= M && p2 <= R){
        help.push_back(nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++]);
    }
    while(p1 <= M){
        help.push_back(nums[p1++]);
    }
    while(p2 <= R){
        help.push_back(nums[p2++]);
    }
    for(int i = 0; i < help.size(); i++){
        nums[L + i] = help[i];
    }
}

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。

例：

[1, 3, 4, 2, 5]
1: 0
3: 1
4: 1 + 3
2: 1
5: 1 + 3 + 4 + 2
all = 0 + 1 + 4 + 1 + 10 = 16
int merge(vector<int>& arr, int L, int M, int R){
    vector<int> help;
    int p1 = L;
    int p2 = M + 1;
    int res = 0;
    while (p1 <= M && p2 <= R){
        res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;
        // 相等时先拷贝右组
        help.push_back(arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]);
    }
    while(p1 <= M){
        help.push_back(p1++);
    }
    while (p2 <= R){
        help.push_back(p2++);
    }
    for(int i = 0; i < help.size(); i++){
        arr[L + i] = help[i];
    }
    return res;
} 
int process(vector<int>& arr, int L, int R){
    if(L == R){
        return 0;
    }       
    int mid = L + ((R - L) >> 1);
    return process(arr, L, mid) + process(arr, mid + 1, R) + merge(arr, L, mid, R);
}
int smallSum(vector<int>& arr){
    if(arr.size() < 2){
        return 0;
    }
    return process(arr, 0, arr.size() - 1);
}

类似问题：逆序对

int mod = (int) 1e9 + 7;
int InversePairs(vector<int> data) {
    if(data.size() < 2){
        return 0;
    }
    return process(data, 0, data.size() - 1) % mod;
}
int process(vector<int>& data, int L, int R){
    if(L == R){
        return 0;
    }
    int mid = L + ((R - L) >> 1);
    return process(data, L, mid) % mod + 
        process(data, mid + 1, R) % mod + merge(data, L, mid, R) % mod;
}
int merge(vector<int>& data, int L, int M, int R){
    vector<int> help;
    int p1 = L;
    int p2 = M + 1;
    int res = 0;
    while(p1 <= M && p2 <= R){
        res = (res + (data[p1] < data[p2] ? 0 : (R - p2 + 1))) % mod;
        help.push_back(data[p1] < data[p2] ? data[p2++] : data[p1++]);
    }
    while(p1 <= M){
        help.push_back(data[p1++]);
    }
    while(p2 <= R){
        help.push_back(data[p2++]);
    }
    for(int i = 0; i < help.size(); i++){
        data[L + i] = help[i];
    }
    return res % mod;
}

2.3 快速排序

问题1

给定一个数组arr和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求时间复杂度为O(N)，空间复杂度为O(1)。

分两种情况：

(1) arr[i] <= num，arr[i]和 <=区的下一个数交换，<=区右扩，i++

(2) arr[i] > num，i++

vector<int> partition1(vector<int>& arr, int num){
    int less = -1;          // <区右边界
    int more = arr.size();  // >区左边界 
    int i = 0;
    while (i < more){
        if(arr[i] <= num){        //当前值 < 划分值
            swap(arr, ++less, i++);
        }else if(arr[i] > num){  //当前值 > 划分值
            i++;
        }
    }
    return {less + 1, more};
}

荷兰国旗问题：

给定一个数组arr和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求时间复杂度为O(N)，空间复杂度为O(1)。

分三种情况：

(1) arr[i] < num，arr[i]和 <区下一个交换，<区右扩，i++

(2) arr[i] == num，i++

(3) arr[i] > num，arr[i]和 >区前一个交换，>区左扩，i不变

vector<int> partition2(vector<int> & arr, int num){
    int less = -1;          // <区右边界
    int more = arr.size();  // >区左边界
    int i = 0;
    while (i < more){
        if(arr[i] < num){        //当前值 < 划分值
            swap(arr, ++less, i++);
        }else if(arr[i] > num){  //当前值 > 划分值
            swap(arr, --more, i);
        }else{
            i++;
        }
    }
    return {less + 1, more};
}

快速排序：

1.0版本：把最后一个数作为划分值num，<=num的放在左边，>num的放在右边，将num与>num区域的第一个数做交换，左右分别递归

2.0版本：把最后一个数作为划分值num，<num的放在左边，=num的放中间，>num的放在右边，将num与>num区域的第一个数做交换，左右分别递归

时间复杂度：O(N^2)

3.0版本：在数组中随机选择一个数，与最后一个数交换作为划分值num

时间复杂度：O(NlogN)

✅tested

void quickSort(vector<int>& nums, int L, int R){
    if(L < R){
        srand((unsigned)time(NULL));
        swap(nums, L + rand()%(R - L + 1), R);  //在数组中随机选择一个数，与最后一个数交换作为划分值num
        vector<int> p = partition(nums, L, R);  //根据实际的数据状况决定
        quickSort(nums, L, p[0] - 1);
        quickSort(nums, p[1] + 1, R);
    }
}
//返回值：等于区域的左边界和右边界
vector<int> partition(vector<int>& nums, int L, int R){
    int less = L - 1;   // <区右边界
    int more = R;       // >区左边界
    while(L < more){
        if(nums[L] < nums[R]){      //当前值 < 划分值
            swap(nums, ++less, L++);
        }
        else if(nums[L] > nums[R]){ //当前值 > 划分值
            swap(nums, --more, L);
        }
        else{
            L++;
        }
    }
    swap(nums, more, R);
    return {less + 1, more};
}
void swap(vector<int>& nums, int i, int j){
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp; 
}

2.4 堆排序

逻辑上完全二叉树

  • 定义：对一棵具有 n 个结点的二叉树按层序编号，编号为 i (1<=i<=n)的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同

  • 把从0出发连续的一段，想象成二叉树

  • i

    • 左：2*i+1
    • 右：2*i+2
    • 父：(i - 1)/2

大根堆

  • 堆结构（重要）
  • 优先级队列结构 就是 堆结构

✅tested

// 某个数现在处在index位置，往上继续移动
void heapInsert(vector<int>& arr, int index){
    while (arr[index] > arr[(index - 1) / 2]){  //当前的数大于父位置的数
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
//某个数在index位置，能否往下移动
void heapify(vector<int>& arr, int index, int heapSize){
    int left = index * 2 + 1;   //左孩子的下标
    while (left < heapSize){ 
        //两个孩子中，谁的值大，把下标给largest
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        //父和较大的孩子之间，谁的值大，把下标给largest
        largest = arr[largest] > arr[index] ? largest : index;
        if(largest == index){
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}

堆排序

先将整个数组变成大根堆，把最大值和堆的最后一个位置做交换，heapsize--，剩下的进行heapify，继续把最大值和堆的最后一个位置做交换，heapsize--

✅tested

void heapSort(vector<int>& arr){
    if(arr.size() < 2){
        return;
    }  
    // 用户一次只给一个数: O(NlogN)
    for (int i = 0; i < arr.size(); i++){   //O(N)
        heapInsert(arr, i); //O(logN)
    }
    // 用户一次给出所有的数: O(N)
    // for (int i = arr.size() - 1; i >= 0; i--){
    //     heapify(arr, i, arr.size());
    // }
    int heapSize = arr.size();
    swap(arr, 0, --heapSize);       //0位置的数与堆上最后一个数做交换
    while (heapSize > 0){           //O(N)
        heapify(arr, 0, heapSize);  //O(logN)
        swap(arr, 0, --heapSize);   //O(1)
    }
}

小根堆

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

思路：假设k=6，准备一个小根堆，首先遍历前7个数，小根堆的最小值一定在0位置。

复杂度：O(N*logk)

void sortedArrDistanceLessK(vector<int>& arr, int k){
    // 默认大根堆，greater -> 小根堆
    priority_queue<int, vector<int>, greater<int>> q;
    int index = 0;
    for(; index <= min((int)arr.size(), k); index++){
        q.push(arr[index]);
    }
    int i = 0;
    for(; index < arr.size(); i++, index++){
        q.push(arr[index]);
        arr[i] = q.top();
        q.pop();
    }
    while (!q.empty()){
        arr[i++] = q.top();
        q.pop();
    }
}