- 正确答案：要实现“去重并从小到大排序数组”，可以先对数组进行排序，然后使用双指针法去除重复元素；或者更简便地，使用集合（Set）结构去重后再转为列表并排序。最终返回一个不含重复元素且按升序排列的数组。 - 解答思路： 1. 首先考虑输入是一个整数数组（可能包含重复元素）。 2. 目标是输出一个新数组，满足两个条件：无重复元素、升序排列。 3. 可行方案有两种主要思路： a) 先排序，再遍历去重（适合空间受限场景） b) 利用哈希结构去重，再排序（代码简洁，常用） 4. 在手撕代码时，推荐写出两种解法，并能分析其时间与空间复杂度。 - 深度知识讲解：考点一：去重的数据结构选择 - 使用 Set（如 C++ 的 unordered_set，Java 的 HashSet，Python 的 set）可以在 O(1) 平均时间内判断元素是否已存在，从而实现 O(n) 时间去重。 - 但 Set 不保证顺序，因此需要额外排序。考点二：排序算法的选择 - 若使用内置排序（如 sort()），平均时间复杂度为 O(n log n)，基于快速排序或归并排序的优化实现（如 Introsort）。 - 若手动实现排序，可考察快排或归并排序的编码能力。考点三：双指针去重技巧（适用于有序数组） - 当数组已经排序后，所有相同元素会相邻。 - 使用两个指针：slow 指向当前应填入不重复元素的位置，fast 遍历整个数组。 - 若 arr[fast] != arr[slow]，则将 arr[fast] 放到 arr[slow+1]，slow 后移。 - 最终 [0...slow] 即为去重后的结果。考点四：稳定性和原地操作 - 本题不要求稳定性，也不强制原地操作，但若要求节省空间，则应采用“排序 + 双指针原地去重”。 - 代码示例（C++风格伪代码，通用性强）：方法一：使用集合去重 + 排序 ``` vector removeDuplicatesAndSort(vector& nums) { set unique_set(nums.begin(), nums.end()); vector result(unique_set.begin(), unique_set.end()); return result; } ``` 时间复杂度：O(n log n)，因为 set 插入每个元素耗时 O(log n) 空间复杂度：O(n) 方法二：先排序 + 双指针去重（原地） ``` vector removeDuplicatesAndSort(vector& nums) { if (nums.size() == 0) return {}; // Step 1: sort the array sort(nums.begin(), nums.end()); // Step 2: use two pointers to remove duplicates int slow = 0; for (int fast = 1; fast < nums.size(); fast++) { if (nums[fast] != nums[slow]) { slow++; nums[slow] = nums[fast]; } } // Step 3: resize the vector to contain only unique elements nums.resize(slow + 1); return nums; } ``` 时间复杂度：O(n log n) — 主要由排序决定空间复杂度：O(1) — 原地操作，仅用常量额外空间 - 扩展知识点： 1. 如果数据范围较小（例如元素值在 [0, 100] 内），可以使用计数排序思想： - 创建大小为 101 的布尔数组 seen[] - 遍历原数组标记出现过的数字 - 按索引从小到大输出即可得到去重且有序的结果 - 时间复杂度 O(n + k)，k 是值域大小，空间换时间示例（值域已知）： ``` vector countSortUnique(vector& nums) { bool seen[101] = {false}; for (int x : nums) { seen[x] = true; } vector result; for (int i = 0; i <= 100; i++) { if (seen[i]) { result.push_back(i); } } return result; } ``` 2. 函数式编程写法（Python一行解）： sorted(list(set(nums))) 3. 流式处理（Java 8 Streams）： nums.stream().distinct().sorted().collect(Collectors.toList()); 4. 边界情况注意： - 空数组处理 - 单元素数组 - 全部元素相同的情况 - 总结：面试中建议优先写“排序 + 双指针”方法，体现对底层操作的理解；也可提及其他方法做对比。重点展示对时间/空间权衡、STL原理、以及边界处理的能力。

快手前端日常一面

全站热榜

创作者周榜