跳转至

4.2 查找和排序

查找和排序都是程序设计中经常用到的算法。

查找相对简单,

**查找**包括 顺序查找,二分查找,哈希表查找,二叉树查找

在面试的时候,不管是用循环还是递归,面试官都期待应聘者能够信手捏来写出完整的二分查找代码, 否则来面试的兴趣都没有

哈希表和二叉排序树查找的重点在于考查对应的数据结构而不是算法

  • 哈希表最注意的优点是我们能在O(1)的时间内查找某一元素, 是效率最高的查找方式, 但缺点是需要额外的空间来实现哈希表.
  • 与二叉排序树查找算法对应的数据结构是二叉搜索树(面试题33, 36)

排序相对复杂

面试官经常会要求应聘者比较插入排序, 冒泡排序, 归并排序, 快速排序等不同算法的优劣.

强烈建议应聘者在准备面试的时候, 一定要对各种排序算法的特点烂熟于胸, 能够从额外空间消耗, 平均时间复杂度和最差时间复杂度等方面去比较他们的优缺点

很多公司的面试官喜欢在面试环节要求应聘者写出快速排序的代码, 应聘者不妨自己写一个快速排序的函数并测试.

快速排序

快速排序的思想:

选取一个主元, 遍历数组, 将大于主元的数放在主元的右边, 将小于主元的数放在主元的左边, 再递归对两遍的分区进行同样的操作.

void Swap(int& a, int& b)
{
    int t = a;
    a = b;
    b = t;
}
int Partion(int* arr, const int begin, const int end);

void QuickSort(int* arr, const int begin, const int end)
{
    if (begin < end)
    {
        int pivot_index = Partion(arr, begin, end);
        QuickSort(arr, begin, pivot_index);
        QuickSort(arr, pivot_index+1, end);
    }
}

int Partion(int* arr, const int begin, const int end)
{
    int pivot_index = begin;
    int pivot = arr[pivot_index];
    int left = begin + 1;
    int right = end - 1;

    while(true)
    {
        while(left <= right && arr[left] <= pivot)
            left ++;

        while(left <= right && arr[right] > pivot)
            right --;

        if(left > right)
            break;
        else
            Swap(arr[left], arr[right]);
    }
    Swap(arr[pivot_index], arr[right]);
    return right;
}

不同的排序算法适用的场合也不尽相同, 快速排序虽然总体的平均效率最好, 但也不是任何时候都是最优的算法, 比如数组本身已经排好序了, 而每一轮排序的时候都以最后一个数字作为标准, 此时快速排序的效率只有O(n^2).

因此, 在这种场合快速排序就不是最优的算法, 在面试的时候, 如果面试官要求实现一个排序算法, 那么应聘者一定要问清楚这个排序的应用环境是什么, 有哪些约束条件, 在得到足够多的信息之后再选择最合适的算法.

面试题11: 旋转数组的最小数字

Question

把一个数组最开始的若干元素搬到数组的末尾, 我们称之为数组的旋转; 输入一个递增排序的数组的一个旋转, 输出旋转数组的最小元素; 例如, 数组{3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转, 该数组的最小值为1

传送门,leetcode 官方视频题解,很详细: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-by-leetcode-s/

参考代码: FindRotatedArrayMin