Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

这个BFPRT算法找逻辑Bug找了两天

注意点:

  1. 在找中位数的时候对传入的数组进行排序,这里使用直接插入排序,因为元素个数最多为5,插排常数项极低
    1. 注意:这里不是nums[j] > nums[i]而是for j = i - 1; j >= start && nums[j] > temp; j--,因为后面会对nums[i]造成修改
  2. 找中位数数组的中位数medianOfMedians返回的是最终的中位数的值,我们使用这个值进行Partition,自己这里还一直将其当做返回的索引用,导致越界
  3. BFPRT函数调用自己的时候,参数一定要对应,自己在写的时候直接将k传入了start

题目描述

使用一个固定长度大小的数组实现栈

思路

思路:使用一个index进行指向当前可以插入元素的位置
  1. 使用一个index指向下次栈中加入元素的位置
  2. 如果要弹出元素,需要判断index是否大于1,如果大于弹出index-1位置的元素,index减去1,否则不可以弹出。
  3. 如果要加入元素,直接加入到index指向的位置,之后index++

题目描述

使用一个固定长度大小的数组实现队列

思路

思路:使用start指向队头,end指向队尾的下一个位置
  1. 我们加了一个标志位empty区分start等于end的两种情况,一种是队列中没有元素,另外一种是队列元素满。
  2. 如果要弹出元素,需要判断end是否等于start,如果empty为真且start等于end,说明不可以弹出,否则可以弹出元素。
  3. 如果要加入元素,直接加入到end指向的位置,之后end需要判断是否处于最后一个位置,如果是则跳转到数组第1个位置,否则end++。同时判断是否满元素来更新empty

题目描述

给定一个数组,求如果排序之后,相邻两数的最大差值,要求时 间复杂度O(N),且要求不能用非基于比较的排序

注意不基于比较哦

思路

思路:桶排序
  1. 假设数组长度为n,准备n+1个桶
  2. 遍历该数组,将最小值放入到第1个位置,将最大值放入到最后一个位置
  3. 将剩下的数等分成等分成n-1份依次放入剩下对应范围的桶中,
  4. 最后这n+1个桶中至少有一个空桶,说明桶内的数值差不是最大差值,我们去桶间找最大差值
  5. 对于每个桶,我们都保存了每个桶的最小值和最大值,从第2个桶开始,每次计算当前桶的最小值与前一个桶(要有元素)的最大值的差,过程中我们动态更新最大差值

堆排序基本知识

基本介绍

堆是一个完全二叉树,因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树:

  1. 下标为i的节点的左子节点的下标为i*2+1, 右子节点的下标为i*2+2
  2. 下标为i的节点的父节点的下标为(i-1)/2

建立堆的时间复杂度:O(log1) + O(log2) + … + O(logN) 近似于 O(N),因此建立堆的时间复杂度为O(N)

堆有大根堆以及小根堆,没有规定堆中左子树的根必须大于(或小于)右子树的根。

堆排序的两个基本步骤:(具体说明看代码注释)
  1. 建堆,循环将数组中的每个数加入堆中(每次都需要heapInsert)
  2. 不断从堆的最后一个元素交换到堆的头部,然后将堆的长度减小1,再调整堆,每次都需要heapify

题意

逆序对,如果前面的元素大于后面的元素则为一个逆序对,统计一个数组中逆序对的个数并返回

思路

思路:每次遇到左半边数组的元素大于右边数组元素,说明产生逆序对

产生逆序对的个数为:(mid - 左边数组元素当前下标 + 1)。说明有这么多个元素是大于当前右边数组这个元素。

一句话总结就是:如果右半部分数组当前元素小于左半部分数组的当前元素,那么当前左半部分数组的当前元素后面的元素(包括当前元素)都是大于右半部分数组当前元素的,也就是统计左半部分数组当前元素后面元素(包括当前元素)有多少个即可。

例如:左半部分数组为1,3,4 右半部分数组为1,2,5
那么如果当前左半部分数组元素为3,右半部分数组当前元素为2,此时产生的逆序对便是左半部分数组元素3右边所有的元素(包括3这个元素)

使用归并排序来对小和问题进行求解

步骤

因为归并排序已经将数组分成了两个已经有序的子数组,我们要想统计小和的个数,我们就需要在merge的过程中统计小和的个数。

假设本次要merge两个子数组为num1, num2。分别为num的左右两个子数组,其中num1的下标从0到mid,num2的下标从mid+1到right

  1. 如果每次合并的时候num2中的元素num2[j]小于num1中的元素num1[i],此时会产生小和
    1. 对于num1中的元素num1[i],此时比它大的有num2中的第j个元素之后的所有元素(包括num2的第j个元素)。这里我们不考虑num1中比num1[i]大的元素,因为我们在生成有序num1的时候就已经考虑过了。
    2. 所以此时num2中大于num1[i]元素个数为(r-j+1),但是要统计小和,所以我们让之前统计小和的结果加上(r-j+1)* num1[i]
    3. 不断循环,知道整个数组都已经归并完成
  2. 上面第1步是合并了num的从l到j的元素,但是我们还要不断递归

几个关键点

  1. return mergeSort(nums, l, mid) + mergeSort(nums, mid+1, r) + merge(nums, l, mid, r) 这里是我们统计左边半个数组内部的小和以及右边半个数组内部的小和,以及左右两个子数组合并时候产生的小和

  2. ret += (r-j+1) * nums[i] 因为是要求小和,所以我们统计出了比num[i]小的元素个数为(r-j+1)个,最后还是要乘以nums[i]来获取nums[i]的两个数组之间的小和

应用场景

  1. 求小和
  2. 求逆序对的个数

几个注意点:

mid := l + (r-l)>>1 避免数组越界

for i <= mid { help[index] = nums[i] index++ i++ },这里是一个for循环,不是if,因为是要将后面剩下的数拷贝进来

for i <= mid { help[index] = nums[i] index++ i++ },这里是一个for循环,不是if,因为是要将后面剩下的数拷贝进来

冒泡排序

思路:从左向右每次两两比较相邻元素,如果前一个元素大于后一个元素,那么就交换这两个元素,一趟下来肯定有一个元素放到了最后的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func BubbleSort(nums []int) []int {
bubbleSort(nums)
return nums
}

func bubbleSort(nums []int) {
//从前往后进行交换,每次都会固定好后面的元素
for i := 0; i < len(nums)-1; i++ {
for j := 0; j < len(nums)-1-i; j++ {
//两两比较并交换
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1], nums[j]
}
}
}
}

选择排序

思路:每次选择一个当前未排序的最小元素放到当前未排序的第一个位置上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func SelectSort(nums []int) []int {
selectSort(nums)
return nums
}

func selectSort(nums []int) {
//存储最小元素对应的下标
var min int
//进行多少趟
for i := 0; i < len(nums)-1; i++ {
min = i
//每趟从哪里开始
j := i + 1
for ; j < len(nums)-1; j++ {
if nums[min] > nums[j] {
min = j
}
}
if min != i {
nums[i], nums[min] = nums[min], nums[i]
}
}
}