位运算:
1)有一个数组只包含这样的数,有几个数出现偶数次,有1个数出现奇数次,要求时间复杂度不超过o(n),怎么求出现奇数次的数。
使用 ^ 异或运算整个数组,偶数次运算结果为0,只留下最后一个奇数次的数。
2 ) 有一个数组只包含这样的数,有几个数出现偶数次,有2个数出现奇数次,要求时间复杂度不超过o(n),怎么求出现奇数次的两个数。
对数组进行^运算求出最后 两个奇数的和eor。
eor提取出二进制最右的1 记为rightOne。
eor & (~eor + 1)
rightOnt 对整个数组分组,只保留和eor最右为1一样的元素。
因为a,b两个奇数不相等,a^b的结果至少二进制上有一位不相等,一个是0,一个是1。也就是eor的最右为1的一样的元素。
对分组后的一个数组求异或就得到其中一个奇数。
插入排序
有n个元素的数组
第一次循环从0开始,到1结束,从0到1实现有序。进行了一次比较。
第二次循环从0开始,到2结束,从0到2实现有序。进行了二次比较。
第n次循环从0开始,到n-1结束,从0到n-1实现有序。进行了n次比较。
n次循环,n次比较,时间复杂度为 o(n^2).
二分法
类似求极限的的思维,每次二分都排除一部分数,最终逼近准确值。