一、知识点 数组 二分查找 二、解题思路 左边界从0开始，右边界从len-1开始。 若nums[mid]>nums[mid+1]，则说明波峰在左边，将right置为mid； 若nums[mid]<=nums[mid+1]，则说明波峰在右边，将left置为mid+1。 最后的退出条件left==right，返回left即可。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int fi...

一、知识点 数组 数学 二、解题思路 从左下角开始，若array[i][j]<target，则j++。 若array[i][j]>target，则i--。 时间复杂度O(n+m)，空间复杂度O(1)。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param target int整型 * @param array int整型vector<vector<>> * @return bool布尔型 */ bool Find(int target,...

一、知识点 数组 二分查找 二、解题思路 左边界left从0开始，右边界从len-1开始， 不断将nums[mid]与target作比较，直到left>right。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int search(vector<int>& nums, int target) { int len = num...

一、知识点 数组 滑动窗口 二、解题思路 最外层遍历数据，a+b+c=0转换为b+c=-a。 左边界left设为i+1，右边界right设为len-1。 不断缩小窗口范围寻找满足条件的b和c，注意跳过相邻的重复数字。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num int整型vector * @return int整型vector<vector<>> */ vector<vector<int> > threeS...

一、知识点 数组 数学 二、解题思路 遍历数组，若nums[i]>=1 && nums[i]<=len时， 通过不断交换，最后使得nums[i]出现在下标nums[i]-1的位置。 最后遍历数组，若i+1!=nums[i]，则返回i+1即可。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int minNumberDisappeared(vector<int&...

一、知识点 数组 数学 二、解题思路 初始化xorVal为0，遍历数组将所有元素做异或运算，得出两个不同数字的异或结果。 从二进制最低位开始，找到xorVal第一个二进制位为1的位置。 将原数组按照该位进行分组，求每组出现一次的数字。 最后判断下两个数字的大小，保持升序输出。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型vector */ vector<int> FindNumsAppe...

一、知识点 数组 数学 二、解题思路 用ret代表数组中超过一半的数，cnt代表它出现的次数。 遍历数组，当i为0或者cnt为0时，更新ret的值和cnt； 否则当ret==numbers[i]时，cnt++，反之cnt--。 最后ret即为所求。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param numbers int整型vector * @return int整型 */ int MoreThanHalfNum_Solution(vector<int>&...

一、知识点 哈希表 数组 二、解题思路 遍历数组的同时，查找target-numbers[i]的值是否在hash表内。 不存在则将numbers[i]放入hash表，否则查找到的hash表的第二个元素（即second val）和当前的i满足题意返回。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param numbers int整型vector * @param target int整型 * @return int整型vector */ vector<int> ...

一、知识点 数组 排序 二、解题思路 1.思路一 快速排序 将数组进行快速排序 时间复杂度O(nlogn)，空间复杂度O(1)。 2.思路二 计数排序 新建一个hash映射，遍历原数组统计0、1、2分别出现的次数。 最后根据hash构造新数组。 时间复杂度O(n)，空间复杂度O(n)。 三、C++解法 1.快排 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cows int整型vector * @return int整型vector */ vector<int> so...

一、知识点 数组 快排 二、解题思路 利用快排思想，第k小数前面都比它小，后面都比它大。 根据pos和k的相对位置，每次只继续处理一边的顺序。 时间复杂度O(n)，空间复杂度O(1)。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param weights int整型vector * @param k int整型 * @return int整型 */ int findKthSmallest(vector<int>& weights, int k) { i...

一、知识点 数组 快排 二、解题思路 快速排序模板题 时间复杂度O(nlogn)，空间复杂度O(1) 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cows int整型vector * @return int整型vector */ vector<int> sortCows(vector<int>& cows) { int len = cows.size(); qucikSort(cows, 0, len - 1); return c...

一、知识点 数组 模拟 二、解题思路 preVal标记前一个元素的值，count记录相同元素的个数。 当i==0或者当前元素与preVal不相等时，更新preVal和count的值。 时间复杂度O(n)，空间复杂度O(1)。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int remove_duplicates_v3(vector<int>& nums) { int le...

一、知识点 数组 数学 二、解题思路 先翻转0到k-1的元素，再翻转k到len-1的元素，最后反转0~len-1的元素即可。 时间复杂度O(n)，空间复杂度O(1)。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param k int整型 * @return int整型vector */ vector<int> rotate_left(vector<int>& nums, int k) { ...

一、知识点 数组 模拟 二、解题思路 val标记整数，count标记val出现的次数。 当count为0时，更新val。 时间复杂度O(n)，空间复杂度O(1)。 三、C++解法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int majority_cow(vector<int>& nums) { int len = nums.size(); int count = 0, val = -...