数据结构与算法面经
1.Top K解决办法。
- 全局排序,O(n*lg(n))
- 局部排序(冒泡前k个),只排序前k个,O(n*k);
堆排序,前k个也不用排序了。维护一个k个元素的小顶堆,进入新的元素不断与小顶堆的root比较,最终得到的就是未排序的前k个元素,O(n*lg(k))
随机选择+partition.通过随机选择,找到arr[1, n]中第k大的数,再进行一次partition,就能得到TopK的结果。
分治法:每个分支都要递归,例如快速排序
快速排序算法思想(分治法:把一个大的问题,转化为若干个子问题(Divide),每个子问题“都”解决,大的问题便随之解决)。
1
2
3
4
5
6void quick_sort(int[]arr, int low, inthigh){
if(low== high) return;
int i = partition(arr, low, high);//快速排序的核心,会用数组arr中的一个元素(默认是第一个元素t=arr[low])为划分依据,将数据arr[low, high]划分成左右两个子数组:左半部分,都比t大;右半部分,都比t小;中间位置i是划分元素
quick_sort(arr, low, i-1);
quick_sort(arr, i+1, high);
}
减治法:把一个大的问题,转化为若干个子问题(Reduce),这些子问题中“只”解决一个,大的问题便随之解决(Conquer)。只需要递归一个分支解决问题,例如二分查找O(lg(n)),随机选择O(n);
二分查找思想(减治法):
1
2
3
4
5
6
7
8
9int BS(int[]arr, int low, inthigh, int target){
if(low> high) return -1;
mid= (low+high)/2;
if(arr[mid]== target) return mid;
if(arr[mid]> target)
return BS(arr, low, mid-1, target);
else
return BS(arr, mid+1, high, target);
}随机选择算法(找出第K大的数):
在第一次partition后:i = partition(arr, 1, n);
- 如果i大于k,则说明arr[i]左边的元素都大于k,于是只递归arr[1, i-1]里第k大的元素即可;
- 如果i小于k,则说明说明第k大的元素在arr[i]的右边,于是只递归arr[i+1, n]里第k-i大的元素即可;
随机选择算法伪代码:
1
2
3
4
5
6
7
8
9int RS(arr, low, high, k){
if(low== high) return arr[low];
i= partition(arr, low, high);
temp= i-low; //数组前半部分元素个数
if(temp>=k)
return RS(arr, low, i-1, k); //求前半部分第k大
else
return RS(arr, i+1, high, k-i); //求后半部分第k-i大
}
2.各种排序算法介绍。
详见博客:https://www.cnblogs.com/flyingdreams/p/11161157.html
- 交换排序:
- 冒泡排序
- 快速排序
- 插入排序:
- 简单插入排序
- 希尔排序(缩小增量排序)
- 选择排序
- 简单选择排序
- 堆排序
- 归并排序
排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
插入排序 | O(n^2) | O(n) | O(1) | 稳定 | |
希尔排序 | O(n^1.5) | O(n^2) | O(n) | O(1) | 不稳定 |
选择排序 | O(n^2) | O(1) | 不稳定 | ||
堆排序 | O(nlgn) | O(1) | 不稳定 | ||
冒泡排序 | O(n^2) | O(n) | O(1) | 稳定 | |
快速排序 | O(nlgn) | O(n^2) | O(nlgn) | 不稳定 | |
归并排序 | O(nlgn) | O(n) | 稳定 |
注:未写复杂度的和平均是一样的。
选择排序和冒泡的区别:冒泡交换相邻元素,每一次找到最大的;选择排序是直接找到最大的,然后放到已排序的末尾。
快速排序思路:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
1 | void quickSort(vector<int>& arr, int low, int high) |
归并排序思路:将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。它使用了递归分治的思想;相当于:左半边用尽,则取右半边元素;右半边用尽,则取左半边元素;右半边的当前元素小于左半边的当前元素,则取右半边元素;右半边的当前元素大于左半边的当前元素,则取左半边的元素。
1 | private static void mergeSort(int[] array) { |