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;  }

---

暂时更新到这里，博主会持续更新的