小米算法高频题面经：快速排序原理、两数之和(哈希表一次遍历)、有效的括号(栈的应用)

小米算法高频题面试：小米Android开发覆盖MIUI系统定制、IoT设备互联。技术栈偏底层，面试官喜欢问系统级原理和性能数据。技术方向偏向MIUI定制、IoT互联。特色专项包括MIUI系统定制与IoT设备开发。今天8道题覆盖小米算法高频题面试核心考点。Q1：快速排序原理？分治：选pivot→根据pivot分区(左边小于pivot，右边大于)→递归排左右子数组。平均O(nlogn)，最坏O(n²)(已排序数组+最后一个元素做pivot)。优化：随机选pivot或三数取中。fun quickSort(arr: IntArray, low: Int = 0, high: Int = arr.lastIndex) { if (low gt;= high) return val pivot = partition(arr, low, high) quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high) }深度解析：从复杂度看，分治：选基准 partition 成两半再递归。平均 O(n log n)，最坏 O(n²)（已有序且选端点的基准）。。常见变体与延伸包括：三数取中优化基准、堆排序（稳定 O(n log n)）、TopK 用快排思想 O(n)。。实战要特别注意边界情况：近乎有序数据要随机化基准，否则退化。。面试官大概率会接着追问：怎么用快排思想在 O(n) 平均时间内找第 K 大？为什么平均是 O(n)？。追问：为什么实际工程中快排比归并排序更常用？快排空间O(logn)(