给你一个未排序的整数数组 nums
,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n)
并且只使用常数级别额外空间的解决方案。
要找到未排序的整数数组中没有出现的最小正整数,并且要求使用 O(n) 时间复杂度和常数级别额外空间,可以通过数组索引的映射来实现。
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 将所有正整数放到对应的索引位置
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
// 查找第一个索引位置与数值不对应的情况
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
给你一个整数数组 nums
,返回 数组 answer
,其中 answer[i]
等于 nums
中除 nums[i]
之外其余各元素的乘积 。
题目数据 保证 数组 nums
之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法,**且在 O(*n*)
时间复杂度内完成此题。
在不使用除法并且在 O(n) 时间复杂度内完成此题的要求下,可以使用两次遍历来实现。具体思路如下:
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] result = new int[n];
// 第一次遍历,计算每个元素左边所有元素的乘积
int left = 1;
for (int i = 0; i < n; i++) {
result[i] = left;
left *= nums[i];
}
// 第二次遍历,右边所有元素的乘积与之前计算的结果相乘得到最终结果
int right = 1;
for (int i = n - 1; i >= 0; i--) {
result[i] *= right;
right *= nums[i];
}
return result;
}
}
给定一个整数数组 nums
,将数组中的元素向右轮转 k
个位置,其中 k
是非负数。
要将数组中的元素向右轮转k个位置,可以通过三次反转数组的操作来实现。
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n; // 如果k大于数组长度,取余数
// 翻转整个数组
reverse(nums, 0, n - 1);
// 翻转前k个元素
reverse(nums, 0, k - 1);
// 翻转剩余的元素
reverse(nums, k, n - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}