数组：交换
睡不醒的鲤鱼 2021-05-26 每日一题 LeetCode
# 0041. 缺失的第一个正数 (opens new window)
题目
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
桶排序的思想，将每个元素放在其对应的位置上，之后遍历数组，遇到第一个错位元素就是最小的正整数。
代码
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
// 将元素放在对应下标上
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
// 寻找第一个不正确位置的元素下标
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) return i + 1;
}
return n + 1;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 0189. 旋转数组 (opens new window)
题目
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
解析
代码
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k %= nums.size();
reverse(nums, 0, nums.size() - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.size() - 1);
}
void reverse(vector<int>& nums, int start, int end) {
while (start < end) {
swap(nums[start++], nums[end--]);
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 0280. 摆动排序 (opens new window)
题目
给你一个无序的数组 nums, 将该数字 原地 重排后使得 nums[0] <= nums[1] >= nums[2] <= nums[3] ...。
解析
根据题意可知，奇数位的数字不小于相邻的偶数位数字，根据这个规律，遍历数组，遇到不满足要求的数字交换即可。
代码
class Solution {
public:
void wiggleSort(vector<int>& nums) {
for (int i = 1; i < nums.size(); i ++) {
if ((i % 2 == 1 && nums[i] < nums[i - 1]) || (i % 2 == 0 && nums[i] > nums[i - 1])) {
swap(nums[i], nums[i - 1]);
}
}
}
};
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10