这篇文章上次修改于 258 天前,可能其部分内容已经发生变化,如有疑问可询问作者。

LC35. 搜索插入位置

简单

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

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

二分查找(O(log n))

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    const len = nums.length
    let left = 0,
        right = len
    
    while (left < right) {
        const mid = Math.floor(left + (right - left)/2)
        if (nums[mid] < target) {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return left
};

循环暴力(O(n))

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    const len = nums.length

    for (let i = 0; i < len; i++) {
        if (nums[i] >= target) return i
    }


    return len
};

LC34. 在排序数组中查找元素的第一个和最后一个位置

中等

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

进阶:

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

二分查找(O(log n))

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    const first = findFirst(nums, target)
    if (first === -1) return [-1, -1]
    const last = findLast(nums, target)
    return [first, last]
};

function findFirst(nums, target) {
    let left = 0,
        right = nums.length - 1

    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2)
        if (nums[mid] < target) {
            left = mid + 1
        } else {
            right = mid
        }
    }

    if (nums[left] === target) return left
    return - 1
}

function findLast(nums, target) {
    let left = 0,
        right = nums.length - 1

    while (left < right) {
        const mid = Math.floor(left + (right - left + 1) / 2)
        if (nums[mid] > target) {
            right = mid - 1
        } else {
            left = mid
        }
    }

    return left
}

循环暴力(O(n))

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let cur = 0
    let first = -1,
        last = -1
    while (cur < nums.length) {
        if (nums[cur] === target) {
            first = cur
            break
        }
        cur ++
    }

    if (first === -1) return [-1, -1]

    while (nums[cur] === target) {
        last = cur ++
    }

    return [first, last]
};

LC153. 寻找旋转排序数组中的最小值

中等

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

示例 1:

输入:nums = [3,4,5,1,2]
输出:1
示例 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0
示例 3:

输入:nums = [1]
输出:1
提示:

1 <= nums.length <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数都是 唯一 的
nums 原来是一个升序排序的数组,但在预先未知的某个点上进行了旋转

二分查找

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    const len = nums.length
    let left = 0,
        right = len - 1

    if (nums[len - 1] > nums[0]) return nums[0]

    if (len === 1) return nums[0]

    while (left <= right) {
        const mid = Math.floor(left + (right - left + 1) / 2)
        if (nums[mid] < nums[mid - 1]) {
            return nums[mid]
        } else if (nums[mid] > nums[0]) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

};

二分查找优化(二分排除)

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    const len = nums.length
    let left = 0,
        right = len - 1

    if (len === 1 || (nums[len - 1] > nums[0])) return nums[0]

    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2)
        if (nums[mid] >= nums[0]) {
            left = mid + 1
        } else {
            right = mid
        }
    } 
    return nums[left]
};

二分查找优化(二分循环)

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    const len = nums.length
    let left = 0,
        right = len - 1
    
    if (len === 1 || (nums[len - 1] > nums[0])) return nums[0]

    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2)
        if (nums[mid] < nums[mid - 1]) {
            return nums[mid]
        } else if (nums[mid] > nums[mid + 1]) {
            return nums[mid + 1]
        } else if (nums[mid] > nums[0]) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

};

LC154. 寻找旋转排序数组中的最小值 II

困难

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1:

输入: [1,3,5]
输出: 1
示例 2:

输入: [2,2,2,0,1]
输出: 0
说明:

这道题是 寻找旋转排序数组中的最小值 的延伸题目。
允许重复会影响算法的时间复杂度吗?会如何影响,为什么?

二分查找(二分排除)

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    const len = nums.length
    let left = 0,
        right = len - 1
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2)
        if (nums[mid] > nums[right]) {
            left = mid + 1
        } else if (nums[mid] < nums[right]) {
            right = mid
        } else {
            right --
        }
    }

    return nums[left]
};

注意找到真正最小的存在,进行比较

LC33. 搜索旋转排序数组

中等

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转(例如, [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] )。

请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1

示例 1:

输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:

输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:

输入:nums = [1], target = 0
输出:-1
提示:

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4

二分查找(二分循环)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    const len = nums.length
    let left = 0,
        right = len - 1
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2)
        if (target === nums[mid]) return mid
        else if (nums[mid] >= nums[left]) {
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return -1
};

LC81. 搜索旋转排序数组 II

中等

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
进阶:

这是 搜索旋转排序数组 的延伸题目,本题中的 nums  可能包含重复元素。
这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?

二分查找(二分循环)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function(nums, target) {
    const len = nums.length
    let left = 0,
        right = len - 1
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2)

        if (nums[mid] === target) return true

        if (nums[mid] === nums[left]) {
            left ++
            continue
        }
        if (nums[mid] >= nums[left]) {
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return false
};

LC278. 第一个错误的版本

简单

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

假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5,并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以,4 是第一个错误的版本。

二分查找(二分排除)

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let left = 0,
            right = n
        
        while (left < right) {
            const mid = Math.floor(left + (right - left) / 2)
            const res = isBadVersion(mid)
            if (res) {
                right = mid
            } else {
                left = mid + 1
            }
        }

        return left
    };
};

LC852. 山脉数组的峰顶索引

简单

符合下列属性的数组 arr 称为 山脉数组 :
arr.length >= 3
存在 i(0 < i < arr.length - 1)使得:
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ,返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

示例 1:

输入:arr = [0,1,0]
输出:1
示例 2:

输入:arr = [0,2,1,0]
输出:1
示例 3:

输入:arr = [0,10,5,2]
输出:1
示例 4:

输入:arr = [3,4,5,1]
输出:2
示例 5:

输入:arr = [24,69,100,99,79,78,67,36,26,19]
输出:2
提示:

3 <= arr.length <= 104
0 <= arr[i] <= 106
题目数据保证 arr 是一个山脉数组

进阶:很容易想到时间复杂度 O(n) 的解决方案,你可以设计一个 O(log(n)) 的解决方案吗?

二分查找(二分排除)

/**
 * @param {number[]} arr
 * @return {number}
 */
var peakIndexInMountainArray = function(arr) {
    const len = arr.length
    let left = 0,
        right = len - 1

    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2)
        if (arr[mid] > arr[mid + 1]) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
};

LC1095. 山脉数组中查找目标值

困难

(这是一个 交互式问题 )

给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。

如果不存在这样的下标 index,就请返回 -1。

何为山脉数组?如果数组 A 是一个山脉数组的话,那它满足如下条件:

首先,A.length >= 3

其次,在 0 < i < A.length - 1 条件下,存在 i 使得:

A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[A.length - 1]

你将 不能直接访问该山脉数组,必须通过 MountainArray 接口来获取数据:

MountainArray.get(k) - 会返回数组中索引为k 的元素(下标从 0 开始)
MountainArray.length() - 会返回该数组的长度

注意:

对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外,任何试图规避判题系统的解决方案都将会导致比赛资格被取消。

为了帮助大家更好地理解交互式问题,我们准备了一个样例 “答案”:https://leetcode-cn.com/playground/RKhe3ave,请注意这 不是一个正确答案。

二分查找(分段处理)

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * function MountainArray() {
 *     @param {number} index
 *     @return {number}
 *     this.get = function(index) {
 *         ...
 *     };
 *
 *     @return {number}
 *     this.length = function() {
 *         ...
 *     };
 * };
 */

/**
 * @param {number} target
 * @param {MountainArray} mountainArr
 * @return {number}
 */
var findInMountainArray = function(target, arr) {
    const len = arr.length()
    
    const peak = findPeak(arr, len)
    // console.log(peak)
    if (arr.get(peak) === target) return peak
    const left = findLeft(arr, peak, target)
    console.log(left)
    if (left !== -1) return left
    const right = findRight(arr, peak, len, target)
    console.log(right)
    return right
};

function findRight(arr, peak, len, target) {
    let left = peak + 1,
        right = len - 1
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2)
        const val = arr.get(mid)
        if (val === target) return mid
        if (val > target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

function findLeft(arr, peak, target) {
    let left = 0,
        right = peak - 1 
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2)
        const val = arr.get(mid)
        console.log(val)
        if (val === target) return mid
        else if (val > target) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    return -1
}

function findPeak(arr, len) {
    let left = 0,
        right = len - 1
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2)
        const val = arr.get(mid),
              next = arr.get(mid + 1)
       
        if (val < next) {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return left
}