如果笔记

如果笔记

做有价值的技术笔记

【算法第1期】数组操作常用思路:左右夹击

本文从 LeetCode 上找了 3 个数组相关的题,从这些题的解法里总结了一个思路:左右夹击,很多数组相关的题都可以用到这种思路

**左右夹击,就是遍历数组时从左右两边同时向中间逼近,需要两个指针,一个指向数组第一个元素,一个指向数组最后一个元素,通过循环把两个指针向中间移动。** 我们先从一个简单的题开始吧,**LeetCode 第 344 题**:把数组逆序,例如输入`[1, 2, 3, 4]`,要求输出`[4, 3, 2, 1]`。数组本身有逆序方法`reverse`,但既然是说算法,自然是不能直接用这个方法。 数组操作几乎都要涉及到交换两个元素,先把这个函数写出来: ```javascript function swap(arr, i, j) { const temp = arr[i] arr[i] = arr[j] arr[j] = temp } ``` 回到第 344 题,数组逆序的方法比较简单,其中之一就是:依次交换第一个与最后一个元素,第二个与倒数第二个元素,第三个与倒数第三个元素……直到数组中部,就完成了逆序。 这就可以用**左右夹击**这种思路:左指针指向第一个元素,右指针指向最后一个元素,交换后,左指针移到第二个元素,右指针移到倒数第二个元素……如此循环。代码如下: ```javascript var reverseString = function (s) { let i = 0, j = s.length - 1 while (i < j) { swap(s, i++, j--) } } ``` 解读:左指针`i`指向第一个元素,右指针`j`指向最后一个元素,第一次交换后,递增 i 指向第二个元素,递减 j 指向倒数第二个元素,如此不停移动左右指针直到最中间。i 等于或大于 j 说明到达中间。 这就是左右夹击最典型的例子,左右夹击的循环条件都可以这么写:`while (i < j)`。 下面增加题目难度,看 **LeetCode 第 345 题**:把一个字符串里的元音字母逆序,例如输入`hello`,要求输出`holle`,输入`leetcode`,要求输出`leotcede`。 这也是逆序,不过加了个条件,只把元音字母逆序,但这也可以用左右夹击的思路。 不管三七二十一,我们先把上面的代码拷贝下来,稍微改下就是我们的代码架子: ```javascript // 定义元音字母表,方便判断一个字母是不是元音 const vowels = { a: true, o: true, e: true, i: true, u: true, A: true, O: true, E: true, I: true, U: true, } var reverseVowels = function (s) { // 输入是字符串,先把字符串变成数组 s = s.split('') let i = 0, j = s.length - 1 while (i < j) { } // 输出时还原为字符串 return s.join('') } ``` 接着分析如何只逆序元音字母。可以先从左边找到第一个元音字母,再从右边找到最后一个元音字母,交换,然后……是不是跟前面那题一样! 从左边找到元音字母,可以称为**左边条件成熟**,左边成熟时再从右边找到元音字母便可立即交换,继续写代码: ```javascript var reverseVowels = function (s) { s = s.split('') let i = 0, j = s.length - 1 let ready = false // false 表示左边条件不成熟,true 表示成熟 while (i < j) { if (ready) { // todo } else { // 从左边查找元音字母,找到则改变成熟标识,没找到则移动左指针 if (vowels[s[i]]) { ready = true } else { i++ } } } return s.join('') } ``` 左边代码写完,接着补充右边: ```javascript if (ready) { // 左边条件成熟,开始从右边查找 if (vowels[s[j]]) { // 找到了右边的元音,先交换,同时移动左右指针 swap(s, i++, j--) // 然后重置条件成熟标识,以进行下一轮的查找 ready = false } else { j-- } } else { if (vowels[s[i]]) { ready = true } else { i++ } } ``` 最终代码如下: ```javascript const vowels = { a: true, o: true, e: true, i: true, u: true, A: true, O: true, E: true, I: true, U: true, } var reverseVowels = function (s) { s = s.split('') let i = 0, j = s.length - 1 let ready = false while (i < j) { if (ready) { if (vowels[s[j]]) { swap(s, i++, j--) ready = false } else { j-- } } else { if (vowels[s[i]]) { ready = true } else { i++ } } } return s.join('') } ``` 现在你应该充分理解左右夹击这种思路了! 接下来再看一题巩固一下,**LeetCode 第 905 题**:把一个数组里所有偶数排到所有奇数前面,例如输入`[3, 1, 2, 4]`,要求输出`[2, 4, 1, 3]`,其中偶数的顺序可以随意,奇数的顺序也可以随意。 稍微分析下,思路还是像上面那题,从左边找到第一个奇数,再从右边找到最后一个偶数,交换,再进行下一次查找。就不再赘述了,把上面的代码拷贝下来**改下条件判断**(判断元音改为判断奇偶)即可: ```javascript var sortArrayByParity = function (s) { let i = 0, j = s.length - 1 let ready = false while (i < j) { if (ready) { if ((s[j] & 1) === 0) { swap(s, i++, j--) ready = false } else { j-- } } else { if (s[i] & 1) { ready = true } else { i++ } } } return s } ``` > `(s[j] & 1) === 0`可判断 s[j] 是不是偶数,`s[i] & 1`可判断 s[i] 是不是奇数,利用位运算比除以 2 效率更高。 当然,如果不用 ready 这个变量,可以把代码简少为: ```javascript var sortArrayByParity = function (s) { let i = 0, j = s.length - 1 while (i < j) { if ((s[i] & 1) === 0) { i++ } else if (s[j] & 1) { j-- } else { swap(s, i++, j--) } } return s } ``` 代码是少了,但多了一些重复计算,在寻找右边偶数的过程中,左边 i 位置也要跟着做重复判断。代码少不代表计算量小。 ### 复杂度 以上算法的时间复杂度都是 O(n),空间复杂度都是 O(1),是最优的了。 ### 总结 左右夹击的基本结构: ```javascript var someFunc = function (s) { let i = 0, j = s.length - 1 let ready = false while (i < j) { if (ready) { if (/* 判断右边条件 */) { /* 类似 swap(s, i++, j--) 这样的业务处理,注意移动左右指针 */ ready = false } else { j-- } } else { if (/* 判断左边条件 */) { ready = true } else { i++ } } } return s } ``` 类似这样的要把数组分类为两部分的需求,比如奇偶分开、正负分开等等,都可以用左右夹击的思路,LeetCode 上还有很多题也可以这么去解,等着你去实践吧。 --- ### 其他解法 LeetCode 344: ```javascript var reverseString = function (s) { const mid = s.length >> 1 for (let i = 0; i < mid; i++) { swap(s, i, s.length - i - 1) } } ``` `s.length >> 1`表示除以 2 并向下取整,等于`Math.floor(s.length / 2)`。 LeetCode 905: 其他解法 1: ```javascript var sortArrayByParity = function (s) { let i = 0, j = s.length - 1 while (i < j) { (s[i] & 1) ? swap(s, i, j--) : i++ } return s } ``` 这种算法虽然代码量最少,但进行了太多不必要的交换操作。其做法是从左边开始,只要遇到奇数,就跟右边的数交换,不管右边那个是奇数还是偶数,而交换之后,i 指针原地不动,j 指针向左移动一位。下次循环的时候再判断换到 i 位置的是奇数还是偶数,如果是奇数接着交换,这就有点多余了。例如输入全是奇数的数组`[1, 3, 5]`,这种算法就先交换 1 和 5 变成`[5, 3, 1]`,然后再交换 5 和 3 变成`[3, 5, 1]`(最终输出)。而用左右夹击的算法就不会做任何交换。 > 在算法的世界里,代码少并不意味着效率高。在整个代码的世界里也是这样的。 其他解法 2: ```javascript var sortArrayByParity = function (s) { const n = s.length for (let i = 0, j = 0; i < n; i++) { // 如果 s[i] 是偶数 if (s[i] % 2 === 0) { i > j ? swap(s, i, j++) : j++ } } return s } ``` 这种思路也是划分数组元素的一种常用的解法:两个指针 i、j 都从数组起始位置开始,i 用来遍历数组,j 指向应该被交换的元素(此题中要把奇数放到数组后部分,所以应该指向奇数)。算法过程:依次判断每一个元素,遇到偶数的时候,如果 i 大于 j,则交换 i 和 j 所指元素,交换后 j 指向下一位,否则把 j 指向下一位;遇到奇数不用管。 这种解法平均交换次数仍然比左右夹击的思路要多。例如`[1, 2, 4]`,此解法要交换 2 次,左右夹击只需交换 1 次。 ### 附 [LeetCode 344: Reverse String](https://leetcode.com/problems/reverse-string/) [LeetCode 345: Reverse Vowels of a String](https://leetcode.com/problems/reverse-vowels-of-a-string/) [LeetCode 905: Sort Array By Parity](https://leetcode.com/problems/sort-array-by-parity/)

JS

算法

hahaboy