查找与搜索

二分查找

问题描述

有一长数组，其中的数字都有序，现在给一个数字，要你从该数组中找出该数的索引值，如果数字不存在，则返回 -1。

求解思路

先初始化边界，low 为左边界，high 为右边界，datas 为数组，target 为要查找的目标值，执行下面循环：

如果 low <= high，取出中间值 mid= low + (high-low)/2，然后用 datas[mid] 和 target 比较：

• datas[mid]== target：直接返回 mid。
• datas[mid]> target：说明 target 可能存在左边区间，high = mid-1，继续循环。
• datas[mid]< target：说明 target 可能存在右边区间，low = mid+1，继续循环。

代码实现

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

两数之和

问题描述

如果有一个整数数组 nums 和一个目标值 target，如何在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

求解思路

借助 map，key 为元素的值，value 为元素的下标，将数字不断放进 map，放之前判断里面是否存在 target-num。

代码实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let map = new Map();
  for (let i = 0, len = nums.length; i < len; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]), i];
    } else {
      map.set(nums[i], i);
    }
  }
  return [];
};

二维数组中的查找

问题描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

求解思路

倘若直接暴力遍历，在最坏的情况是遍历完所有的元素才能获取结果。如果这个数组规模是 n * m，那么时间复杂度就是 O(n*m)。我们换一种思路，从右上角开始遍历，当前元素小于目标元素根据数组特点，当前行中最大元素也小于目标元素，因此进入下一行
当前元素大于目标元素根据数组特点，行数不变尝试向前一列查找，这样一来，最坏的结果就是 O(n+m)。

代码实现

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
 var findNumberIn2DArray = function(matrix, target) {
    const rowNum = matrix.length;
    if (!rowNum) {
        return false;
    }
    const colNum = matrix[0].length;
    if (!colNum) {
        return false;
    }

    let row = 0,
        col = colNum - 1;
    while (row < rowNum && col >= 0) {
        if (matrix[row][col] === target) {
            return true;
        } else if (matrix[row][col] > target) {
            --col;
        } else {
            ++row;
        }
    }

    return false;
};

寻找最大的第k个数

问题描述

输入 n 个整数，找出其中最大的 K 个数。例如输入 4, 5, 1, 6, 2, 7, 3, 8 这 8 个数字，则最大的 4 个数字是 5, 6, 7, 8。

求解思路

利用快速排序思想，n 为数组的长度
数组中的第 1 大元素，是，从小到大排序后 n - 1 位置上的元素
数组中的第 k 大元素，即，从小到大排序后 n - k 位置上的元素
我们希望位置 n - k 的左边是比它小的，右边是比它大的，那么 nums[n - k] 就是第 k 大的元素
我们把 n-k 看作 pivot ，用快速排序的手法去 partition “分区”

代码实现

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
 var findKthLargest = function (nums, k) {
    let K = nums.length - k;
    let start = 0, end = nums.length - 1;
 
    while (start < end) {
        let p = partition(nums, start, end);
        if (p === K) {
            return nums[p];
        } else if (p < K) {
            start = p + 1
        } else {
            end = p - 1;
        }
    }
    return nums[start];
  };
  
  function partition(nums, start, end) {
    let random=Math.floor(Math.random() * (end - start + 1) + start)
    swap(nums,start,random)
    let pivot=nums[start]
    while (start < end) {
        while (nums[end] >= pivot && start < end) {
            end--;
        };
        nums[start] = nums[end];
        while (nums[start] < pivot && start < end) {
            start++;
        }
        nums[end] = nums[start];
    }
    nums[start] = pivot;
    return start;
  }
  
  // 快速排序中使用 swap 的地方比较多，我们提取成一个独立的函数
  function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }

二叉搜索树的第k大节点

求解思路

二叉搜索树的中序遍历是一个有序序列

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
 const kthLargest = (root, k) => {
    // 遍历顺序(访问右节点在前)：右-根-左
    const unInOrder = node => {
        if (!node) return;
        unInOrder(node.right);
        res.push(node.val);
        unInOrder(node.left);
    };
    const res = [];
    unInOrder(root, res);
    // 得到从大到小排序的数组
    return res[k - 1];
};