上海的广告公司网站建设,技术支持东莞网站建设机械,wordpress修改省略图,管理咨询公司名字题一#xff1a;旋转数组
给定一个整数数组 nums#xff0c;将数组中的元素向右轮转 k 个位置#xff0c;其中 k 是非负数。
思路一#xff1a;
创建reverse()函数传入三个值分别为数组地址#xff0c;从第几个数组元素开始#xff0c;结束元素位置#xff1b;
在r…
题一旋转数组
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。
思路一
创建reverse()函数传入三个值分别为数组地址从第几个数组元素开始结束元素位置
在reverse函数中实现颠倒swap()函数实现交换。
先将数组分为两部分0--(k-1)和k--(sz-1),然后分别旋转
//交换位置
void swap(int* a, int* b) {int t *a;*a *b, *b t;
}
//实现颠倒
void reverse(int* nums, int start, int end) {while (start end) {swap(nums[start], nums[end]);start 1;end - 1;}
}
//起始位置
void rotate(int* nums, int numsSize, int k)
{int sz numsSize;int i 0;int j 0;int tmp 0;k k % sz;reverse(nums,0,sz-1);reverse(nums,0,k-1);reverse(nums,k,sz-1);}
思路二
如图 void rotate(int* nums, int numsSize, int k)
{int* tmp (int*)malloc(sizeof(int) * numsSize);k numsSize % k;memcpy(tmp, nums numsSize - k, sizeof(int) * k);memcpy(tmpk, nums, sizeof(int) * (numsSize - k));memcpy(nums, tmp , sizeof(int) * numsSize);
}
题二消失的数字
数组nums包含从0到n的所有整数但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗
思路一 将0--n的数全部加起来然后减去数组中的值最后得到的结果就是消失的数。
int missNumber(int* nums, int numsSize)
{int N numsSize;int ret N * (N 1) / 2;for (int i 0; i N; i){ret - nums[i];}return ret;
}
思路二 单身狗问题解法异或“ ^ ”
时间复杂度O(N)
解法定义一个数tmp为0与0--n的数进行异或然后与题所给的数组进行再次异或
得出消失的数
基础a^a0;a^b^ab;
int missingNumber(int* nums, int numsSize)
{int n numsSize;int i 0;int tmp 0;for(i 0; i n;i ){tmp ^ i;}for(i 0;i n;i){tmp ^ nums[i];}return tmp;
}
题三移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
// nums 是以“引用”方式传递的。也就是说不对实参作任何拷贝
int len removeElement(nums, val);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i 0; i len; i) {print(nums[i]);
}
思路一 解题思路 1. 从前往后遍历nums找到val第一次出现的位置 2. 将val之后的所有元素整体往前搬移即删除该val 3. nums中有效元素个数减少一个 循环进行上述操作直到nums中所有值为val的元素全部删除完 时间复杂度:O(N^2) 空间复杂度:O(1)
int removeElement(int* nums, int numsSize, int val) {// while (1){// 1. 在nums中找val出现的位置int pos 0;for (; pos numsSize; pos){if (nums[pos] val){break;}}// 2. 检测是否找到if (pos numsSize)break;// 3. 找到值为value的元素--将其删除for (int j pos 1; j numsSize; j){nums[j - 1] nums[j];}numsSize--;}return numsSize;
}
思路二 解题思路: 因为题目说了数组中元素个数最大为100所以不用动态申请至二级创建100个元素数组即可 1. 创建一个100个元素的整形数组temp 2. 遍历nums将nums中所有与val不同的元素搬移到temp中 3. 将temp中所有元素拷贝回nums中 时间复杂度: O(N) 空间复杂度: O(N)
int removeElement(int* nums, int numsSize, int val) {// 1. 申请numSize个元素的新空间int temp[100];// 2. 将nums中非value的元素搬移到temp中---尾插到temp中int count 0;for (int i 0; i numsSize; i){if (nums[i] ! val){temp[count] nums[i];count;}}// 3. 将temp中删除val之后的所有元素拷贝到nums中memcpy(nums, temp, sizeof(int) * count);return count;
}
思路三 解题思路: 1. 设置一个变量count用来记录nums中值等于val的元素的个数 2. 遍历nums数组对于每个元素进行如下操作 a. 如果num[i]等于val说明值为val的元素出现了一次count b. 如果nums[i]不等于元素将nums[i]往前搬移count个位置 因为nums[i]元素之前出现过count个值等于val的元素已经被删除了 因此次数需要将nums[i]往前搬移 3. 返回删除之后新数组中有效元素个数 时间复杂度O(N) 空间复杂度O(1)
int removeElement(int* nums, int numsSize, int val) {int count 0;for (int i 0; i numsSize; i){if (nums[i] val){count;}else{nums[i - count] nums[i];}}return numsSize - count;
} 做错的选择题
分析以下函数的时间复杂度
void fun(int n) {int il;while(in)ii*2;
}
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
答案D
解析: 此函数有一个循环但是循环没有被执行n次i每次都是2倍进行递增所以循环只会被执行log2(n)次。 给定一个整数sum从有N个有序元素的数组中寻找元素ab使得ab的结果最接近sum最快的平均时间复杂度是
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
答案A 解析此题目中数组元素有序所以a,b两个数可以分别从开始和结尾处开始搜根据首尾元素的和是否大于sum,决定搜索的移动整个数组被搜索一遍就可以得到结果所以最好时间复杂度为n 分析以下函数的空间复杂度 int** fun(int n) {int ** s (int **)malloc(n * sizeof(int *));while(n--)s[n] (int *)malloc(n * sizeof(int));return s;}
A.O(n)
B.O(n^2)
C.O( 1 )
D.O(nlogn) 解析此处开辟的是一个二维数组数组有n行每行分别有1,2,3,...n列所以是n(n 1)/2个元素空间空间复杂度为n^2
