基础算法:二分查找、异或运算
作为一名程序员,不管是前端、后端、运维、测试、数据库、算法等等岗位,都是需要学习算法的,不仅能提升编程能力,还能提升思维逻辑、分析问题的能力,是IT职场必不可少的加薪技能。
千里之行,始于足下,最好的学习时间是一年前,其次是现在。最近在网上学习左程云老师的算法基础,记录下我的学习结果。
二分查找
例子1:有序数组某元素最左位置
给你一个n代表有一个长度为n的有序数组,然后给你一个k,你需要判断这个k是否在数组里面,如果存在就返回这个数从左往右第一次出现位置的下标,如果不存在输出-1。
思路:数组有序,所以可以使用二分查找,期间如果找到k,则下标赋给临时变量index,直到切成唯一元素(l === r),比较后返回。最终index为输出值。
let index = -1;
find(0, N - 1, key, list);
// 有序数组arr里,下标从 l 到 r 之间,二分查找最左的key。
// 递归法:
const find = (l, r, key, arr) => {
if (l > r) return;
if (l === r) {
if (arr[l] === key) index = l;
return;
}
// 二分
let middle = l + ((r - l) >> 1);
if (arr[middle] > key) {
find(l, middle - 1, key, arr)
}
if (arr[middle] === key) {
index = middle; // 找到临时最左,继续向左找
find(l, middle - 1, key, arr)
}
if (arr[middle] < key) {
find(middle + 1, r, key, arr)
}
}
// 迭代法:
const find = (l, r, key, arr) => {
let middle = 0;
while(l <= r) {
middle = l + ((r-l) >> 1);
if (arr[middle] === key) {
index = middle;
r = middle - 1;
}
if (arr[middle] > key) r = middle - 1;
if (arr[middle] < key) l = miidle + 1;
}
}
二分查找的时间复杂度为:O(logN)。空间复杂度为O(1)。
而普通的从左向右遍历查询代码更简单,但是时间复杂度为:O(N),如下:
const findKey = (l, r, key, arr) => {
let index = -1;
for (let i = l; i < r; i++) {
if (arr[i] === key) { // 从左到右第一个
index = i;
break;
}
if (arr[i] > key) { // 大于则直接退出
break;
}
}
return index;
}
总结:当一个数组有序时候,查找某个元素的位置,或者查找某个元素最左(最右)的位置等等都可以使用二分查找,其时间复杂度为O(logN)。
例子2:有序数组元素>=k的最左位置
你需要输入一个n,一个数k,然后输入一个长度为n个大小的数组arr,然后你需要在arr上找满足>=K的最左位置,并且输出这个位置,如果不存在这个位置就输出-1。
输入描述:
第一行输入一个n,k
第二行输入长度为n的数组arr
思路:与例子1类似,改变一下判断条件即可。
(function(){
// 递归法
const find = (l, r, k, arr)=>{
if (l > r) return;
if (l === r) {
if (arr[l] >= k) index = l;
return;
}
// 二分
let middle = l + ((r - l) >> 1);
if (arr[middle] >= k) {
index = middle; // 找到临时最左,继续向左找
find(l, middle - 1, k, arr)
}
if (arr[middle] < k) {
find(middle + 1, r, k, arr)
}
}
let a = readline().trim(),b = readline().trim();
// 编码
let N = Number(a.split(' ')[0]), k = Number(a.split(' ')[1]),
list = b.split(' ').map((item) => Number(item));
let index = -1;
find(0, N-1, k, list);
print(index)
})();
// 迭代法:
const find = (l, r, key, arr) => {
let middle = 0;
while(l <= r) {
middle = l + ((r-l) >> 1);
if (arr[middle] >= key) {
index = middle;
r = middle - 1;
}else{
l = miidle + 1;
}
}
}
时间复杂度仍然为 O(logN)。
例子3:获取任意一个局部最小元素位置
定义局部最小的概念。arr长度为1时,arr[0]是局部最小。arr的长度为N(N>1)时,如果arr[0] < arr[1],那么arr[0]是局部最小;
如果arr[N-1]<arr[N-2],那么arr[N-1]是局部最小;如果0<i<N-1,既有arr[i] < arr[i-1],又有arr[i] < arr[i + 1],那么arr[i]
是局部最小。给定无序数组arr,已知arr中任意两个相邻的数都不相等,只需要返回arr中任意一个局部最小出现的位置即可,如果不存在这个位置就输出-1。
(function(){
// 迭代法
const find = (l, r, arr)=>{
if(r < 0) return -1
if(r === 0) return 0
if (arr[0]< arr[1]) return 0
if (arr[r] < arr[r-1]) return r
while(l <= r) {
if(l === r) return l
let mid = l + ((r-l) >> 1)
if(arr[mid] < arr[mid-1]) {
if(arr[mid] < arr[mid+1]){
return mid
}else {
l = mid + 1
}
}else {
r = mid - 1
}
}
return -1
}
let N = Number(readline().trim()),b = readline().trim();
// 编码
let list = b.split(' ').map((item) => Number(item));
print( find(0, N-1, list))
})();
异或运算
异或运算性质:
- 一个数异或0,则结果为这个数: a^0 = a。
- 一个数异或它自己,则结果为0: a^a = 0。
- 满足交换律和结合律:a^b^c == (a^b)^c == (a^c)^b。
例子1:找出数组中奇数次出现的一个数
一个数组中有一种数出现了奇数次,其他数都出现了偶数次,怎么找到这一个数?
// N为数组arr的长度
const find = (N, arr) => {
if(N < 1) return -1
let res = 0
for(let i = 0; i < N; i++) {
res ^= arr[i]
}
return res
}
例子2:找出数组中奇数次出现的两个数
给定一个数字arr,其中只有两个数字出现了奇数次,其它数字都出现了偶数次,按照从小到大顺序输出这两个数。
思路:
既然有两个奇数次出现的数,通过所有数字相异或可得出结果为(a^b),而且这两个数(a,b)必然至少有一位(二进制)是不同的,假设这位是第二位,a里为1,b里为0。==则数组中所有第二位为1的数相异或,结果必然为a;同理为0的相异或结果必为b。==
关键就是两点:如何计算ab中第几位不同;如果获取数组中所有第某位(假设称为关键位)为1的数。
// N为数组arr的长度
const find = (N, arr) => {
if(N < 2) return -1
// 初始值,考虑到连续异或,所以设置为0
let a = 0, b = 0, eor = 0
for(let i = 0; i < N; i++) {
// eor值为 a^b
eor ^= arr[i]
}
// 获取ab中最右边位(关键位)为1的值,比如:0010
let point = eor & (~eor + 1)
for(let i = 0; i < N; i++) {
// 如果这个数与 point 相与不为0,则这个数在关键位上为1,全部相异或则结果为a。
if(arr[i] & point !== 0) {
a ^= arr[i]
}
}
b = point ^ a
return a < b ? (a + ' ' + b) : (b + ' ' + a)
}
总结:
两个关键点已经给出,关键点1:获取ab中最右边位(关键位)为1的值 的方式比较特殊:一个数 与上 这个数按位非再加一的数,就是这个数中最右边位为1,其他位为0的数。目的是方便提取关键点2。