有免费做推广的网站吗,建设网站要做的工作内容,ui软件界面设计,网站做菠菜20240531-时间复杂度
1、消失的数字 方法一#xff1a;位运算
两个数字一样的数组#xff0c;其中一个数组中少了一个数字#xff0c;定义一个变量分别异或两个数组#xff0c;结果即为缺少的数字 class Solution {public int missingNumber(int[] nums) {int xor 0;int…20240531-时间复杂度
1、消失的数字 方法一位运算
两个数字一样的数组其中一个数组中少了一个数字定义一个变量分别异或两个数组结果即为缺少的数字 class Solution {public int missingNumber(int[] nums) {int xor 0;int n nums.length;//获取数组长度for (int i 0; i n; i) {//因为该数组少一个数所以i nxor ^ nums[i];}for (int i 0; i n; i) {//假设该数组数字为0~n不少数字所以i nxor ^ i;}//分别遍历两数组进行异或操作相同数字异或得零//其他数字均出现两次只有一个数字出现一次return xor;}}
方法二数学规律
1到n的等差数列的总和减去当前数组元素的总和即为缺少的数字
class Solution {public int missingNumber(int[] nums) {int n nums.length;//等差数列总和 首项 尾项* 项数 / 2int total (1 n) * n / 2;//当前数组的总和int sum 0;for(int i0;in;i){sum nums[i];}//缺少值 等差数列总和 - 数组总和return total - sum;}
} 2、旋转数组 这个不会暂且搁置
3、给定一个整数sum从有N个有序元素的数组中寻找元素ab使得ab的结果最接近sum最快的平均时间复杂度是
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
选B了
解析
正确答案A数组元素有序所以ab两个数可以分别从开始和结尾处开始搜索根据首位元素的和是否大于sum决定搜索的移动整个数组被搜索一遍就可以得到结果所以时间复杂度为O(n)
4、设某算法的递推公式是T(n)T(n-1)nT(0)1则求该算法中第n项的时间复杂度为
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
解析 5、分析以下函数的时间复杂度
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倍进行递增所以只会被执行
6、分析以下函数的空间复杂度
public static int[][] get2Array(int n){int[][] array new int[n][];for(int i 0; i n; i) {array[i] new int[n-i];n--;}return array;
}
A.O(1)
B.O(N)
C.O(N^2)
D.O(logN)
解析
