二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

链接：https://leetcode-cn.com/problems/binary-search/

解法：

  • 方法一：

定义target在一个左闭右闭的区间里，也就是[left,right]
所以有两点：

  • while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

image.png

  1. var search = function(nums, target) {
  2.     let left = 0;
  3.     let right = nums.length - 1; // 定义target在左闭右闭的区间里，[left, right]
  4.     while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
  5.         let middle = left + ((right - left) >>1);// 防止溢出 等同于(left + right)/2
  6.         if (nums[middle] > target) {
  7.             right = middle - 1; // target 在左区间，所以[left, middle - 1]
  8.         } else if (nums[middle] < target) {
  9.             left = middle + 1; // target 在右区间，所以[middle + 1, right]
  10.         } else { // nums[middle] == target
  11.             return middle; // 数组中找到目标值，直接返回下标
  12.         }
  13.     }
  14.     // 未找到目标值
  15.     return -1;
  16. };
  • 方法二：

定义target在一个左闭右开的区间里，也就是[left,right]
所以有两点：

  • while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
  • if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

image.png

  1. var search = function(nums, target) {
  2.   let left = 0;
  3.   let right = nums.length; // 定义target在左闭右开的区间里，即：[left, right)
  4.   while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
  5.       let middle = left + ((right - left) >> 1);
  6.       if (nums[middle] > target) {
  7.           right = middle; // target 在左区间，在[left, middle)中
  8.       } else if (nums[middle] < target) {
  9.           left = middle + 1; // target 在右区间，在[middle + 1, right)中
  10.       } else { // nums[middle] == target
  11.           return middle; // 数组中找到目标值，直接返回下标
  12.       }
  13.   }
  14.   // 未找到目标值
  15.   return -1;
  16. };

第一个错误的版本

是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
链接：https://leetcode-cn.com/problems/first-bad-version/

解法：

  • 方法一：二分查找

将左右边界初始化为1和n，其中n是给定版本的数量，设定左右边界后，每次都依据左右边界找到其中间的版本，检查其是否为正确的版本。如果该版本为正确的版本，那么第一个错误的版本必然位于该版本的右侧，此时缩紧左边界；否则第一个错误的版本必然位于该版本及该版本的左侧，此时缩紧右边界。
这样我们每判断一次都可以缩紧一次边界，而每次缩紧时两边界距离将变为原来的一半，因此我们至多只需要缩紧 O(logn) 次。
复杂度分析
时间复杂度：O(\log n)O(logn)，其中 nn 是给定版本的数量。
空间复杂度：O(1)O(1)。我们只需要常数的空间保存若干变量。

  1. var solution = function(isBadVersion) {
  2.     return function(n) {
  3.         let left=1,right=n
  4.         while(left<right){ // 循环直至区间左右端点相同
  5.             let middle=Math.floor(left + (right - left) / 2); // 防止计算时溢出
  6.             if(isBadVersion(middle)){
  7.                 right=middle // 答案在区间 [left, mid] 中
  8.             }else{
  9.                 left=middle+1 // 答案在区间 [mid+1, right] 中
  10.             }
  11.         }
  12.         // 此时有 left == right，区间缩为一个点，即为答案
  13.         return left
  14.     };
  15. };

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

链接：https://leetcode-cn.com/problems/search-insert-position/

解法：

  • 方法一：二分查找

二分算法最后left和right下标对应的值就是这个数组相邻的两个值
那么在进行最后一次循环(left===right)的时候，一定会找到那个值，也就是nums[left]||nums[right]
但是如果依旧没找到，那么right就会middle-1，就会跳出循环。
这个时候right代表的就是上一个值了，那么这个目标值插入的位置就是此时的left了

  1. var searchInsert = function(nums, target) {
  2.     let left=0;
  3.     let right=nums.length-1
  4.     while(left<=right){
  5.         let middle=left+((right-left)>>1)
  6.         if(nums[middle]===target){
  7.             return middle
  8.         }else if(nums[middle]<target){
  9.             left=middle+1
  10.         }else if(nums[middle]>target){
  11.             right=middle-1
  12.         }
  13.     }
  14.     return left
  15. };

  • 方法二：indexOf()方法

    1. var searchInsert = function(nums, target) {
    2.   const index=nums.indexOf(target)
    3.   if(index>1){
    4.       return index
    5.   }else{
    6.       nums.push(target)
    7.       nums.sort((a,b)=>a-b)
    8.       const index=nums.indexOf(target)
    9.       return index
    10.   }
    11. };

    有序数组的平方

    给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

    1. 输入：nums = [-7,-3,2,3,11]
    2. 输出：[4,9,9,49,121]

    链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array/

    解法：

  • 方法一：暴力法：map+sort，先平方后排序

    1. var sortedSquares = function(nums) {
    2.   if(!nums || nums===null) return nums;
    3.   return nums.map(item=>item*item).sort((a,b)=>a-b)
    4. };

  • 方法二：双指针

题目说的有序数组，有三种情况。
（1）全是负数
-6，-5，-4，-3，-2
（2）全是正数
1，3，4，5，6，7
（3）有正有负
-3，-2，0，5，6，7
我们可发现，不管是（1）（2）（3）的哪种情况，元素的平方最大值一定产生在原数组的最左边或者最右边。
题目要求我们生成一个平方数组，从小到大排好序返回，我们这里已经能够确定平方最大值的产生位置了。
我们将最大值放入平方数组的最后一个位置就好了。

  1. var sortedSquares = function(nums) {
  2.     if(!nums || nums===null) return
  3.     // write得到元素值平方值，从新数组最后位置开始写
  4.     let left=0,right=nums.length-1,write=nums.length-1
  5.     let result=new Array(nums.length)
  6.     // 左右指针相遇（逐渐靠拢的过程）之后不再循环
  7.     while(left<=right){
  8.         // 如果原数组的左指针对应的平方值大于右指针，那么往新数组最后位置写入左指针对应的平方
  9.         if(nums[left]*nums[left]>nums[right]*nums[right]){
  10.             result[write]=nums[left]*nums[left]
  11.             left++;
  12.             // 移动新数组待写入的位置
  13.             write--;
  14.         }else{
  15.             result[write]=nums[right]*nums[right]
  16.             right--;
  17.             write--;
  18.         }
  19.     }
  20.     return result
  21. };

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

  1. 输入: nums = [0,1,0,3,12]
  2. 输出: [1,3,12,0,0]

链接：https://leetcode-cn.com/problems/move-zeroes/

解法：

  • 方法一：一次遍历

这里参考了快速排序的思想，快速排序首先要确定一个待分割的元素做中间点x，然后把所有小于等于x的元素放到x的左边，大于x的元素放到其右边。
这里我们可以用0当作这个中间点，把不等于0(注意题目没说不能有负数)的放到中间点的左边，等于0的放到其右边。
这的中间点就是0本身，所以实现起来比快速排序简单很多，我们使用两个指针i和j，只要nums[i]!=0，我们就交换nums[i]和nums[j]

  1. var moveZeroes = function(nums) {
  2.     let j=0;
  3.     for(let i=0;i<nums.length;i++){
  4.         // 不是0 i和j一起后移 同时交换i和j
  5.         // 如果nums[i]=0 此时j指向的就是0
  6.         if(nums[i]!==0){
  7.             if(nums[j]===0){
  8.                [nums[i],nums[j]]=[nums[j],nums[i]]
  9.             }
  10.             j++
  11.         }
  12.     }
  13.     return nums
  14. };
  • 方法二：双指针

定义两个指针：左指针指向第一个找到的0，右指针指向第一个找到的非0，右指针不断向右移动，每次交换就是将左指针的零和右指针的非零进行交换，同时将左指针右移，且非零数的相对顺序并没有改变。
注意到以下性质：

  1. 左指针左边均为非零数；
  2. 右指针左边直到左指针处均为零。
    1. var moveZeroes = function(nums) {
    2. if(!nums || nums===null) return
    3. let left=0,right=0;
    4. while(right<nums.length){
    5.  if(nums[right]){
    6.       [nums[left],nums[right]]=[nums[right],nums[left]]
    7.       left++;
    8.  }
    9.  right++
    10. }
    11. return nums
    12. };

    合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

    请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
    注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
    链接：https://leetcode-cn.com/problems/merge-sorted-array/

    解法：

  • 方法一：sort+splice ```javascript var merge = function(nums1, m, nums2, n) { if(n===0) return nums1 else{
    1.   if(nums1.length){
    2.       nums1.splice(m,n,...nums2)
    3.       return nums1.sort((a,b)=>a-b)
    4.   }else{
    5.       return nums2
    6.   }
    }

};


- **方法二：逆向双指针**

通过原地修改数组的方式，将空间复杂度降到O(1)，这样不需要考虑额外的数组空间，可以完全把nums2放入nums1中。原地修改时，为了避免从前向后遍历导致原有的数组被破坏，可以从后往前遍历。**这里需要创建三个指针：**<br />第一个指针i指向第一个数组，第二个指针j指向第二个数组，可以用arr[i]和arr[j]进行大小的比较，谁小谁就落在结果数组中，落哪个数组，就把哪个数组的下标向前提一位。再创建指针k,用来控制结果数组的下标
```javascript
var merge = function(nums1, m, nums2, n) {
    let i=m-1,j=n-1,k=m+n-1
    while(i>=0||j>=0){
        if(i<0) nums1[k--]=nums2[j--]
        else if(j<0) nums1[k--]=nums1[i--]
        else if(nums1[i]<nums2[j]) nums1[k--]=nums2[j--]
        else nums1[k--]=nums1[i--]
    }
    return nums1
};

两个数组的交集2

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

// 示例1
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

// 示例2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

解法：

  • 方法一：
    var intersect = function(nums1, nums2) {
  const result=[]
  const hashMap={}
  for(const item1 of nums1){ // 记录nums1各个数字的出现次数
      if(hashMap[item1]){
          hashMap[item1]++
      }else{
          hashMap[item1]=1
      }
  }
  for(const item2 of nums2){
      let value=hashMap[item2]
      if(value>0){              // 有出现过
          result.push(item2)    // 推入结果数组
          hashMap[item2]--      // 匹配一个，就减一个
      }
  }
  return result
};

    买卖股票的最佳时机

    给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

    你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
    返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 ```javascript 输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

**链接：**[https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/)
<a name="jPUGq"></a>
#### 解法：

- **方法一：两层遍历**
   - **思路**
      - 我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）
   - **复杂度分析**
      - 时间复杂度O(n^2)
      - 空间复杂度O(1),只使用了常数个变量
```javascript
var maxProfit = function(prices) {
    let result = 0;
    for (let i = 0; i < prices.length - 1; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            const currentProfit = prices[j] - prices[i]
            if (currentProfit > result) {
                result = currentProfit
            }
        }
    }
    return result
};
  • 方法二：动态规划
    • 题目只问最大利润，没问具体哪一天买，哪一天卖，因此可以用动态规划来解决
      var maxProfit = function(prices) {
let dp=new Array(prices.length) // dp[i]在第 i 天卖出股票可以获得的最大利润
let minPrice=prices[0],result=0
for(let i=1;i<prices.length;i++){
   dp[i]=prices[i]-minPrice>0?prices[i]-minPrice:0
   result=Math.max(result,dp[i]) // 更新最大利润
   minPrice=Math.min(prices[i],minPrice) // 更新股票最低价格
}
return result
};
      优化空间：不开辟数组
      var maxProfit = function(prices) {
let result=0,minPrice=prices[0]
for(let i=1;i<prices.length;i++){
   result=Math.max(result,prices[i]-minPrice)
   minPrice=Math.min(minPrice,prices[i])
}
return result
};

      找到所有数组中消失的数字

      给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

      ```javascript // 示例1 输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6]

// 示例2 输入：nums = [1,1] 输出：[2]

**链接：**[https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/](https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/)
<a name="k3V0d"></a>
#### 解法：

- **方法一：数组下标+includes**
```typescript
var findDisappearedNumbers = function(nums) {
    const result=[]
    for(let i=0;i<nums.length;i++){
        if(!nums.includes(i+1)){
            result.push(i+1)
        }
    }
    return result
};

  • 方法二：利用set，判断缺哪个

    var findDisappearedNumbers = function(nums) {
  const set=new Set(nums)
  const result=[]
  for(let i=1;i<=nums.length;i++){
      if(!set.has(i)) result.push(i)
  }
  return result
};

  • 方法三：Map/hashMap

    var findDisappearedNumbers = function(nums) {
  const map=new Map(),result=[]
  for(let i=0;i<nums.length;i++){
      map.set(nums[i],i)
  }
  for(let i=0;i<nums.length;i++){
     if(!map.has(i+1)){
         result.push(i+1)
     }
  }
  return result
};

    最大数

    给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

    注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。 ```javascript // 示例1 输入：nums = [10,2] 输出：”210”

// 示例2 输入：nums = [3,30,34,5,9] 输出：”9534330”

**链接：**[https://leetcode.cn/problems/largest-number/](https://leetcode.cn/problems/largest-number/)

- **提示**
   - 1 <= nums.length <= 100
   - 0<= nums[i] <= 109
- **解法：快排+String**
   - 比如：String x = "12"; String y = "345";

x 拼接 y = "12345" = x + y;<br />y 拼接 x = "34512" = y + x;<br />因为数字在ASCII码表中是有顺序的，所以利用String的compareTo()方法，可以进行自然顺序的排序。

   - 关于[0,0]这个测试用例，因为我们做的是倒序排序，如果排序后的第一个元素是0，那后面的元素肯定小于或等于0，结合题目提示”0 <= nums[i] <= 109“； 所以判断排序后的数组第一个元素为0，就 return "0" 即可。
```javascript
var largestNumber = function(nums) {
    quickSort(nums,0,nums.length-1)
    return nums[0]=='0'?'0':nums.join('')
};
function quickSort(arr,start,end){
    if(start>=end) return 
    let index=start
    let temp=arr[start]
    for(let i=start;i<=end;i++){
        if(arr[i]+''+temp>temp+''+arr[i]){
            index++
            [arr[index],arr[i]]=[arr[i],arr[index]]
        }
    }
    [arr[start],arr[index]]=[arr[index],arr[start]]
    quickSort(arr,start,index-1)
    quickSort(arr,index+1,end)
    return arr
}