青海省安建设管理部门网站,个人博客网站设计模板,网站分辨率,成都企业网站建设哪家专业目录 一、消失的数字
二、轮转数组
三、 单选题 一、消失的数字
数组nums包含从0到n的所有整数#xff0c;但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在 O(n) 时间内完成吗#xff1f;
注意#xff1a;本题相对书上原题稍作改动
示例 1#xff1a; 输入…目录 一、消失的数字
二、轮转数组
三、 单选题 一、消失的数字
数组nums包含从0到n的所有整数但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在 O(n) 时间内完成吗
注意本题相对书上原题稍作改动
示例 1 输入[3,0,1] 输出2 示例 2 输入[9,6,4,2,3,5,7,0,1] 输出8 代码实现一使用异或运算
int missingNumber(int* nums, int numsSize)
{int ans 0;for (int i 0; i numsSize; i){ans ^ i;}for (int i 0; i numsSize; i){ans ^ nums[i];}return ans;
}
代码实现二使用等差数列求和公式
int missingNumber(int* nums, int numsSize)
{int sum numsSize * (numsSize 1) / 2;for (int i 0; i numsSize; i){sum - nums[i];}return sum;
} 以上两种算法的时间复杂度都是 O(n)空间复杂度都是 O(1)。 二、轮转数组
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。
示例 1 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4] 示例 2 输入nums [-1,-100,3,99], k 2 输出[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100] 提示 1 nums.length 10^5 -2^31 nums[i] 2^31 - 1 0 k 10^5
进阶 尽可能想出更多的解决方案至少有 三种 不同的方法可以解决这个问题。 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗
代码实现一
void rotate(int* nums, int numsSize, int k)
{k % numsSize;int* tmp (int*)malloc(sizeof(int) * k);if (NULL tmp){perror(malloc failed!);return;}// 首先把数组后面的 k 个元素存放到 tmp 指向的临时空间中int j 0;for (int i numsSize - k; i numsSize; i){tmp[j] nums[i];}// 然后把数组前面的 numsSize - k 个元素按从后往前的顺序依次往后移动 k 个位置for (int i numsSize - k - 1; i 0; --i){nums[i k] nums[i];}// 最后再将存放在临时空间中的 k 个元素放回数组中for (int i 0; i k; i){nums[i] tmp[i];}free(tmp);tmp NULL;
} 该算法的时间复杂度是 O(n)空间复杂度是 O(k)。 代码实现二
void reverse(int* nums, int left, int right)
{while (left right){int tmp nums[left];nums[left] nums[right];nums[right] tmp;left;--right;}
}
void rotate(int* nums, int numsSize, int k)
{k % numsSize;reverse(nums, 0, numsSize - k - 1);reverse(nums, numsSize - k, numsSize - 1);reverse(nums, 0, numsSize - 1);
} 该算法的时间复杂度是 O(n)空间复杂度是 O(1)。 分析示例一 1 2 3 4 | 5 6 7即根据 k 将整数数组 nums 分为左右两个部分。 4 3 2 1 | 7 6 5它是分别逆序左右两个部分后得到的结果。 5 6 7 | 1 2 3 4它是整体逆序后得到的结果。 在逆序的过程中越靠后的元素经过逆序后就会越靠前因此整体逆序后左右两部分的元素发生了互换但由于之前已经分别逆序了左右两部分的元素因此在第 3 步后两部分的元素的顺序较一开始没有发生改变。 三、 单选题
给定一个整数 sum从有 n 个有序元素的数组中寻找元素 a, b使得 a b 的结果最接近 sum最快的平均时间复杂度是
A、O(n)
B、O(nlogn)
C、O(n^2)
D、O(logn)
代码实现假设数组是按非递减顺序排列
int* findClosestPair(int* nums, int numsSize, int sum, int* returnSize)
{*returnSize 2;int* ans (int*)malloc(sizeof(int) * 2);if (NULL ans){perror(malloc failed!);return NULL;}int left 0;int right numsSize - 1;int dif INT_MAX;while (left right){int res nums[left] nums[right] - sum;if (abs(res) dif) // 判断是否更新误差{ans[0] nums[left];ans[1] nums[right];dif abs(res);}if (res 0) // 此时 nums[left] nums[x] res 0其中 x rightleft;else if (res 0) // 此时 nums[right] nums[x] res 0其中 x left --right;elsebreak;}return ans;
} 该算法的时间复杂度为 O(n)因此正确答案是 A。
