80. 删除有序数组中的重复项 II
题目描述
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
运行代码
class Solution {
public:
int work(vector<int>& nums,int k){
int len =0;
for(auto num:nums)
if(len <k||nums[len-k]!=num)
nums[len++]=num;
return len;
}
int removeDuplicates(vector<int>& nums) {
return work(nums,2);
}
};代码思路
- 定义了一个类
Solution，其中包含两个函数work和removeDuplicates。removeDuplicates函数是对外提供的接口，它调用了work函数来实现具体的逻辑。work函数实现了删除有序数组中重复项的功能，使得重复项最多出现k次（在本题中k = 2）。
-
removeDuplicates函数：作用是调用work函数并传入参数2，表示要将重复项控制在最多出现两次。最后返回处理后的数组长度。 -
work函数：- 接收两个参数，一个是整数向量
nums，另一个是整数k，表示重复项最多出现的次数。 - 初始化变量
len为0，这个变量用于记录处理后的数组长度。 - 通过遍历输入的
nums数组中的每个元素num：- 如果
len < k，说明当前元素无论如何都应该被保留，因为还没有达到重复项出现的最大次数。 - 如果
nums[len - k]!= num，说明距离当前位置k个位置之前的元素与当前元素不同，即当前元素不是重复项或者重复次数还未达到k，也应该被保留。 - 当满足上述条件之一时，将当前元素
num赋值给nums[len]，并将len加一，实现将不重复或重复次数未达k的元素放置在数组的前len个位置。
- 如果
- 最后返回处理后的数组长度
len。
- 接收两个参数，一个是整数向量
88. 合并两个有序数组
题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
运行代码
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i=nums1.size()-1;
m--;
n--;
while(n>=0){
while(m>=0&&nums1[m]>nums2[n]){
swap(nums1[i--],nums1[m--]);
}
swap(nums1[i--],nums2[n--]);
}
}
};代码思路
一、整体思路
- 这段代码的目的是将两个有序数组
nums1和nums2合并到nums1中，使得合并后的nums1仍然保持非递减顺序。 - 通过从后往前遍历两个数组，比较两个数组中当前位置的元素大小，将较大的元素依次放入
nums1的末尾，从而实现合并。
二、函数分析
-
merge函数：- 接收两个参数，分别是整数向量
nums1、nums1中有效元素的数量m、整数向量nums2、nums2中有效元素的数量n。 - 首先初始化一个指针
i指向nums1的最后一个位置，此时i = nums1.size() - 1。同时将m和n分别减一，使得m和n分别指向nums1和nums2的最后一个有效元素。
- 接收两个参数，分别是整数向量
-
循环处理：
- 进入一个循环，条件是
n >= 0，即只要nums2中还有未处理的元素，就继续循环。 - 在循环内部，首先进入一个内层循环，条件是
m >= 0且nums1[m] > nums2[n]。这意味着只要nums1中还有未处理的元素且当前nums1中的元素大于nums2中的元素，就将nums1中的这个较大元素与nums1的末尾元素交换，并将m和i分别减一。 - 当内层循环结束后，说明
nums1中当前位置的元素小于等于nums2中的元素，或者nums1已经处理完了。此时将nums2中的当前元素与nums1的末尾元素交换，并将n和i分别减一。
- 进入一个循环，条件是
4. 寻找两个正序数组的中位数
题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
运行代码
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
if (n > m) //保证数组1一定最短
{
return findMedianSortedArrays(nums2, nums1);
}
// Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。
int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n; //我们目前是虚拟加了'#'所以数组1是2*n长度
while (lo <= hi) //二分
{
c1 = (lo + hi) / 2; //c1是二分的结果
c2 = m + n - c1;
LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];
if (LMax1 > RMin2)
hi = c1 - 1;
else if (LMax2 > RMin1)
lo = c1 + 1;
else
break;
}
return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
}
};代码思路
一、整体思路
该算法的目的是找到两个正序数组的中位数。整体采用了二分查找的思想，通过不断调整两个数组的划分位置，使得划分后的左右两部分满足特定条件，从而确定中位数的位置。
二、关键变量解释
n和m：分别表示数组nums1和nums2的大小。LMax1、LMax2、RMin1、RMin2：分别表示在当前划分下，数组nums1和nums2划分后的左部分最大值和右部分最小值。c1和c2：分别表示对数组nums1和nums2进行划分的位置。实际上是一个虚拟的划分点，将数组分为左右两部分。lo和hi：二分查找的上下界，初始时lo = 0，hi = 2 * n，表示对数组nums1的划分位置的搜索范围。
三、函数分析
- 首先计算两个输入数组的大小
n和m，如果n > m，则交换两个数组，保证nums1是较短的数组，这样可以减少时间复杂度。 - 接着定义了一系列变量，包括用于二分查找的上下界
lo和hi，以及用于存储划分后左右部分最大值和最小值的变量。 - 进入
while循环进行二分查找，循环条件是lo <= hi。 - 在每次循环中，计算当前的划分位置
c1和c2。根据c1和c2计算出两个数组划分后的左部分最大值和右部分最小值。 - 如果
LMax1 > RMin2，说明当前划分位置不合适，需要将hi更新为c1 - 1，缩小搜索范围；如果LMax2 > RMin1，说明当前划分位置也不合适，需要将lo更新为c1 + 1，扩大搜索范围；如果满足条件，则跳出循环。 - 最后，根据找到的划分位置，计算中位数并返回。如果两个数组的总长度是偶数，则中位数是左右两部分最大值的最大值与左右两部分最小值的最小值的平均值；如果总长度是奇数，则中位数是左部分最大值和右部分最小值中的较小值。