数据结构与算法面经

发表于 | 分类于 | 阅读次数:
字数统计: 1.4k字 | 阅读时长 ≈ 6分钟

数据结构与算法面经

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
      6
      void 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
    9
    int 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
    9
    int 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
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
void quickSort(vector<int>& arr, int low, int high)
{
	int l = low;
	int h = high;
	int base = arr[low]; //选取第一个数为基准
	while (l < h)
	{
		//从后向前比较
		while (l < h && arr[h] >= base) //如果没有比关键值小的，比较下一个
		{
			h--;
		}
		if (l < h)
		{
			swap(arr[l], arr[h]);
			//进行替换后，arr[l]肯定小于base，所以不用再次比较
			l++;
		}
		//从前向后比较
		while (l < h && arr[l] <= base)
		{
			l++;
		}
		if (l < h)
		{
			swap(arr[l], arr[h]);
			h--;
		}
	}
	//此时第一次比较已经结束，关键值位置已经确定为l(l=h)，左边都比关键值小，右边都比关键值大
	//递归
	if (l > low)
		quickSort(arr, low, l - 1);
	if (l < high)
		quickSort(arr, l + 1, high);
}

归并排序思路：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。它使用了递归分治的思想；相当于：左半边用尽，则取右半边元素；右半边用尽，则取左半边元素；右半边的当前元素小于左半边的当前元素，则取右半边元素；右半边的当前元素大于左半边的当前元素，则取左半边的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static void mergeSort(int[] array) {
        int[] aux = new int[array.length];
        sort(array, aux, 0, array.length - 1);
    }

    private static void sort(int[] array, int[] aux, int lo, int hi) {
        if (hi<=lo) return;
        int mid = lo + (hi - lo)/2;
        sort(array, aux, lo, mid);
        sort(array, aux, mid + 1, hi);
        merge(array, aux, lo, mid, hi);
    }

    private static void merge(int[] array, int[] aux, int lo, int mid, int hi) {
        System.arraycopy(array,0,aux,0,array.length);
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i>mid) array[k] = aux[j++];
            else if (j > hi) array[k] = aux[i++];
            else if (aux[j]<aux[i]) array[k] = aux[j++];
            else array[k] = aux[i++];
        }
    }