选择排序、冒泡排序、异或运算
选择排序
数组取数时间复杂度是常数
int a= arr[i]
从数组中获取第i位置的数即获取某个偏移量或距离的数 时间复杂度是一个常数
集合取数时间复杂度不是常数，和数据量有关
int b = list.get(i)
从list集合中获取某一个位置的值 时间复杂度不是一个常数 因为和集合中的数据量有关
集合中的数据越多 耗时越长
先找第一个元素 再找第二个元素 再找第三个元素 ，元素越多，耗时越长
选择排序的时间复杂度
第一次排序是 从0到N-1个数中找最小的值放在第一位 确定了一个最小值
第二次排序是 从1到N-1个数中找最小的值放在第二位 确定了次次小的值
第三次排序是 从2到N-1个数中找最小的值放在第三位 确定了第三小的值
第四次排序是 从3到N-1个数中找最小的值放在第四位 确定了第四小的值
要计算该过程的时间复杂度需要先看下有多少个常数操作
-
每次排序都需要遍历一下
第一次排序遍历数组中所有的值即N次 第二次排序遍历N-1次 第三次排序遍历N-2次 第四次排序遍历N-3次
-
每次遍历都需要比较一下
第一次排序比较了N-1次姑且认为N次 第二次排序比较了N-1次 第三次排序比较了N-2次 第四次排序比较了N-3次
-
把最小值找到并且放到第0下标的位置上
每一次排序都需要1次这样的操作
一共做了这么多次常数操作
因为求等差数列一定有N^2 一定有N项
所以可以写成 a N^2+b N+c
这个就是常数数量的表达式
而时间表达式就是在常数数量级的表达式中不要低级项 只要最高阶级的项 而且忽略掉高级项的系数 所剩下的
所以时间复杂度是O(N^2)的算法
小结
-
当两个时间复杂度不同的算法在评估好坏的时候 时间复杂度越小越好 比如O(N) 比 O(N^2)好
-
同样的时间复杂度比如都是O(N)就要看常数项了
虽然可以估算常数操作发生的具体数量 但每一个常数操作虽然是固定时间 但每个时间是不一样的
比如一个常数项是10 常数操作是乘法 另一个常数项是100 常数操作是位运算 此时没发估计 只能实际测试得出每个常数操作的具体时间
这两个算法 每个算法的常数操作执行O(N)次 每次都进行三个常数次操作 所以这2个算法的时间复杂度都是O(N)的 通过理论比较不出只能实际跑一下
额外空间复杂度
只需要有限几个变量就可以完成算法流程的话 就是额外空间复杂度O(1)
若必须开辟一个额外数组 这个额外数据和原来数组等规模的时候 额外的空间复杂度就是O(N)了
选择排序代码
在i到N-1范围选一个最小值 并且把最小值放到i位置上去
只用到了几个变量 i,j,minindex(每次都会释放)
所以额外空间复杂度是O(1)
冒泡排序
初始数据 3，2，5，4，3，6
下标依此是0,1,2,3,4,5
第一次排序：
0，1位置上的数据比较 谁大谁往右移动
1，2位置比较谁大谁往右移动
依此类推 最后确定位置5上的数据是6
第二次排序确定了位置4上的数据是5
小结
第一次排序在0~N-1个数上 确定了N-1位置上的数
第二次排序在0~N-2个数上 确定了N-2位置上的数
第三次排序在0~N-3个数上 确定了N-3位置上的数
还是一个等差数列 a N^2 + b N + c
还是O(N^2)复杂度的算法
冒泡排序代码
异或运算
相同为0 不同为1
二进制异或也是一样的
异或还可以理解为无进位相加
比如0和1相加是1 1和1项加是0 不进位
异或运算性质
-
0^N=N;N^N=0
0和任何数异或都是N 任何数和自己异或都是0
-
异或运算满足交换律和结合律
a^b=b^a;(a^b)^c=a^(b^c)
-
同样一批数亦或得到的结果和选择谁先谁后去异或无关
a、b值交换
第一行 a=a^b a为甲 b为乙 a=a^b即a=甲^乙，b为乙
第二行 b=a^b
a=甲^乙,b=甲^乙^乙
根据任何一个数异或自己都为0得乙^乙=0
根据任何一个数异或0都为自己得甲^0为甲 所以b=甲
第三行a=a^b 甲^乙^甲=乙
所以就实现了交换数据的效果
用异或的前提是 a和b所指向的内存是两块不同的东西，值可以一样 比如甲=乙
如果内存一样 同样的内存区域和自己异或 值都会变成0了
大厂面试题
要求
时间复杂度O(N)、额外空间复杂度O(1) 只用有限几个变量
2个题目
1）
一个int[]整型数组中只有一种数出现了奇数次
其他数出现偶数次
怎么找到出现了奇数次的数
解题
定义一个变量 int eor=0;
定义一个数组int [a,b,c....]
用这个变量去异或数组中的每一个元素
eor ^ a eor ^ b eor ^ c
最后这个eor就是出现了奇数次的数
比如这个数组是 [2,1,3,1,3,1,3,2,1]
因为异或运算顺序无所谓
等同于 [1,1,1,1,2,2,3,3,3]
4个1异或完是0 2个2异或完是0 3个3异或完是3
代码
原理介绍
比如每个数有5个二进制位
如果最高位的1出现奇数个的话 无进位相加的结果就是1
如果最高位出现偶数次1的话 最终结果就是0
所以最终的结果和某一位上1的个数有关 和顺序没有关系
2）
一个int[]整型数组中两种数出现了奇数次
其他数出现偶数次
怎么找到出现了奇数次的数
假设一个数组中 a和b 出现奇数次 其他的数字others都出现偶数次
如果一个变量eor 从头异或到尾 最终结果是a^b
即先把偶数次异或掉都是0
再和奇数个a异或得到a
再和奇数个b异或得到a^b
又因为是2种数 所以a != b
那么eor一定是不等于0的
即eor 这个32位整数的某一位上至少有一位不等于0
假设eor在第8位上是1
说明a数和b数在第8位上是不一样的
再定义一个变量 eor'
用eor'异或上第8位不是1的那些数
只有某一个数字在第8位不是1才异或进eor‘中 得到a或者b
假设eor'=a 因eor=a^b 所以b=eor^eor'=a^b^a=b