第二次排序确定了位置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
