2025.1.12
88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
我的解题思路 ：题目要求合并后的数组仍然放在nums1上，与合并两个有序链表不同的是，数组的当前位置存储最大值时会覆盖原来的元素，而链表不会，因为链表可以断开再连。我使用的方法是创建数组存储合并后的数据，最后移动语义到nums1上。
其他思路 ：看了官方的另外一种解题思路很巧妙。直接从后往前排序，这样就不用担心元素覆盖的问题，因为本来后面就没元素（或者说都是零）。更巧妙的是，从后往前排时数组1后面剩余的空位置永远够排序，根本不用担心排到最后会覆盖。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> nums(m+n);
int p1 = 0,p2 = 0,cur = 0;
while(p1 < m && p2 < n){
if(nums1[p1] < nums2[p2]){
nums[cur] = nums1[p1];
p1++;
}else{
nums[cur] = nums2[p2];
p2++;
}
cur++;
}
if(p1 == m){
while(p2<n){
nums[cur++] = nums2[p2++];
}
}else{
while(p1<m){
nums[cur++] = nums1[p1++];
}
}
nums1 = std::move(nums);
}
};
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1;
int tail = m + n - 1;
int cur;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
cur = nums2[p2--];
} else if (p2 == -1) {
cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
} else {
cur = nums2[p2--];
}
nums1[tail--] = cur;
}
}
};
|
27. 移除元素
我的思路： 简单。快指针在前面探路找不同与val的值，慢指针在后面赋值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int low = 0,fast = 0;
while(fast < nums.size()){
if(nums[fast]!=val){
nums[low] = nums[fast];
low++;
}
fast++;
}
return low;
}
};
|
26. 删除有序数组中的重复项
我的思路： 简单。快指针在前面探路找不同与val的值，慢指针在后面赋值。关键在于那个值是之前没出现过的值，所以需要个map或者数组记录一下之前出现过哪些值，出现了几次。这里要注意使用map[]索引是如果不存在该元素，则会常见一个默认值为0的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <unordered_map>
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int fast = 0, low = 0;
std::unordered_map<int,int> maps;
while(fast < nums.size()){
if(maps[nums[fast]] < 1){
nums[low] = nums[fast];
low++;
}
maps[nums[fast]]++;
fast++;
}
return low;
}
};
|
80. 删除有序数组中的重复项 II
我的思路： 和26. 删除有序数组中的重复项类似，只是题目改了允许重复一个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <unordered_map>
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int fast = 0, low = 0;
std::unordered_map<int,int> maps;
while(fast < nums.size()){
if(maps[nums[fast]] < 2){
nums[low] = nums[fast];
low++;
}
maps[nums[fast]]++;
fast++;
}
return low;
}
};
|
169. 多数元素
多数元素：返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
我的思路： 多数元素其实就是出现次数最多的元素并且次数>n/2，题目说一定有多数元素，所以直接找最多的元素就行。首先要用一个unordered_map或者数组记录各个元素出现的次数。有两个思路，第一个就是记录的过程中就不断的去比较谁次数多，保留最多的那个。第二种就是先记录，最后再找最大值。
leetcode： :上面我的思路是找出现次数最多的元素，但是针对于多数元素的特殊性质，把元素排序，那么多数元素n/2的位置一定有。 这样就解决了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <unordered_map>
#include <algorithm>
class Solution {
public:
int majorityElement(vector<int>& nums) {
std::unordered_map<int,int> maps;
int item = nums[0],maxsize = 1;
maps[item]++;
int i = 1;
while(i < nums.size()){
maps[nums[i]]++;
if( maps[nums[i]]>maxsize){
maxsize = maps[nums[i]];
item = nums[i];
}
i++;
}
return item;
}
};
#include <unordered_map>
#include <algorithm>
class Solution {
public:
int majorityElement(vector<int>& nums) {
std::unordered_map<int,int> maps;
int i = 0;
while(i < nums.size()){
maps[nums[i]]++;
i++;
}
auto com = [](const std::pair<int,int> &left,const std::pair<int,int> &right){
return left.second < right.second;
};
return std::max_element(maps.begin(),maps.end(),com)->first;
}
};
|
2025.1.13
