LeetCode力扣 面试经典150题 详细题解 (1~5) 持续更新中
目录
1.合并两个有序数组
2.移动元素
3.删除有序数组中的重复项
4.删除排序数组中的重复项 II
5.多数元素
暂时更新到这里，博主会持续更新的
1.合并两个有序数组
题目（难度：简单）：
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
解法一 ：
思路：先合并两个数组，然后通过冒泡排序进行排序
public void merge(int[] nums1, int m, int[] nums2, int n) { // 获取nums1数组的长度 int length1 = nums1.length; // 从nums1的有效元素末尾开始，将nums2的所有元素复制到nums1的剩余空间 for (int i = m; i < length1; i++) { nums1[i] = nums2[i - m]; } // 从nums1的开头开始，进行冒泡排序，以确保整个nums1数组是有序的 for (int i = 0; i < length1 - 1; i++) { if (nums1[i] > nums1[i + 1]) { // 如果当前元素大于其相邻的元素，则交换它们 int tmp = nums1[i]; nums1[i] = nums1[i + 1]; nums1[i + 1] = tmp; } } }解法二：
思路：数组nums1和nums2通过比较的方式填充nums1末尾
public void merge(int[] nums1, int m, int[] nums2, int n) { // 初始化指向nums1和nums2末尾的指针 int i = m - 1; // nums1中有效数据的最后一个索引 int j = n - 1; // nums2中有效数据的最后一个索引 // 初始化指向nums1最终位置的指针 int k = nums1.length - 1; // nums1的末尾索引，也是合并后数组的末尾索引 // 当nums2中还有元素未处理时执行循环 while (j >= 0) { // 如果nums1中还有元素，并且当前nums1元素大于nums2元素 if (i >= 0 && nums1[i] > nums2[j]) { // 将nums1当前元素放到最终位置，并将指针向前移动 nums1[k--] = nums1[i--]; } else { // 否则，将nums2当前元素放到nums1的最终位置，并将指针向前移动 nums1[k--] = nums2[j--]; } } // 循环结束后，nums1包含了合并后的有序数组
}2.移动元素
题目（难度：简单）：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
解法一：
public int removeElement(int[] nums, int val) { int length = 0; // 用于记录非目标值元素的数量，也即新数组的长度 for (int i = 0; i < nums.length; i++) { // 如果当前元素不等于目标值val if (nums[i] != val) { // 将该元素移动到数组的前端（覆盖length位置上的元素） nums[length] = nums[i]; // 更新非目标值元素的数量 length++; } // 如果当前元素等于目标值val，则不做任何操作，直接跳过 } // 返回新数组的长度 return length;
}解法二：
public int removeElement(int[] nums, int val) { // 初始化右指针j为数组末尾的索引 int j = nums.length - 1; // 遍历数组，左指针i从数组开始位置到j之前的位置 for (int i = 0; i < j; i++) { // 如果当前元素等于目标值val if (nums[i] == val) { // 交换当前元素nums[i]与右指针指向的元素nums[j] int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; // 由于已经交换了一个等于val的元素到数组末尾，所以j向左移动一位 j--; // 由于交换后当前位置的元素可能又变成了需要移除的值，所以i也需要向左移动一位 i--; } } // 返回j+1作为新数组的长度，因为j此时指向最后一个有效元素的下一个位置 return j + 1;
}3.删除有序数组中的重复项
题目（难度：简单）：
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。 - 返回
k。
解法一：
public int removeDuplicates(int[] nums) { // 使用双指针p和q，p指向当前不重复序列的末尾，q用于遍历数组 int p = 0; int q = 1; // 当q指针未到达数组末尾时执行循环 while (q < nums.length) { // 如果当前p和q指向的元素不相等，说明找到了一个新的不重复元素 if (nums[p] != nums[q]) { // 如果q和p之间的元素个数大于1，说明有多个重复元素 // 此时，将q指向的元素复制到p的下一个位置，覆盖掉多余的重复元素 if (q - p > 1) { nums[p + 1] = nums[q]; } // p指针前移一位，指向新的不重复序列的末尾 p++; } // q指针前移一位，继续遍历数组 q++; } // 返回新的数组长度，即p+1（因为p指向的是最后一个不重复元素的下一个位置） return p + 1;
}4.删除排序数组中的重复项 II
题目（难度：中等）：
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
解法一：
public int removeDuplicates(int[] nums) { // 获取数组的长度 int length = nums.length; // 初始化指针p和q // p指向新数组的最后一个已处理元素之后的位置 // q从数组的第三个元素开始遍历（索引为2） int p = 0; int q = 2; // 当q指针还没有遍历完整个数组时，继续执行循环 while (q < length) { // 如果p指针指向的元素与q指针指向的元素不同 // 说明找到了一个新的、不重复的元素 if (nums[p] != nums[q]) { // 将这个新元素复制到p指针之后的位置 // 因为p指针指向的是新数组的最后一个已处理元素之后的位置 // 所以新元素应该放在p+2的位置（因为p+1的位置是留给下一个不重复元素的） nums[p + 2] = nums[q]; // 将p指针前移一位，为下一个不重复元素腾出空间 p++; } // q指针无论如何都前移一位，继续遍历数组 q++; } // 返回新数组的长度 // 由于数组索引是从0开始的，所以新数组的长度是p+2 // 其中p是新数组的最后一个已处理元素的位置，所以p+2是新数组的长度 return p + 2;
}5.多数元素
题目（难度：简单）：
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
解法一：
public int majorityElement(int[] nums) { // 初始化候选元素和计数器 int candidate = nums[0]; // 将候选元素初始化为数组的第一个元素 int count = 0; // 计数器 // 遍历数组 for (int num : nums) { // 如果计数器为0，则当前元素为候选元素，并将计数器设为1 if (count == 0) { candidate = num; count = 1; } // 如果当前元素与候选元素相同，则计数器加1 else if (num == candidate) { count++; } // 如果当前元素与候选元素不同，则计数器减1 else { count--; } } // 返回候选元素，即为多数元素 return candidate; }