算法_两数之和&中位数

OBKoro1

发布于 2020-10-27 11:54:42

2820

发布于 2020-10-27 11:54:42

文章被收录于专栏：OBKoro1的前端分享

两数之和

难度：简单

描述：

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。

你需要实现的函数 twoSum 需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。

样例：

给出 numbers = [2, 7, 11, 15], target = 9, 返回 [0, 1].

给出 numbers = [2, 33, 11, 2], target = 4, 返回 [0, 3].

思路分析：

target减去每个元素的值，得出来的值，就是我们要搜索的值。

代码模板：

/**
 * @param numbers: An array of Integer
 * @param target: target = numbers[index1] + numbers[index2]
 * @return: [index1, index2] (index1 < index2)
 */
const twoSum = function(numbers, target) {};

想一想再看答案

代码：

转成对象：

这是别人的一种解法，比下面的解法复杂点，可以看看，扩展一下思路。

/**
 * @param numbers: An array of Integer
 * @param target: target = numbers[index1] + numbers[index2]
 * @return: [index1, index2] (index1 < index2)
 */
const twoSum = function(numbers, target) {
  let map = {};
  // key : the complement (target - num)
  // value: index for that num
  for (let i = 0; i < numbers.length; i++) {
    const num = numbers[i];
    if (map[num] !== undefined) {
      // 找到值
      return [map[num], i]; // 第一次保存的index 和 刚找到的下标 即结果。
    } else {
      // 第一次进入 保存 要搜索的值和index
      map[target - num] = i; // 第一次
    }
  }
  return [-1, -1];
};
console.log(twoSum([2, 7, 11, 15], 9), twoSum([2, 33, 11, 2], 4));

双循环

const twoSum = function(numbers, target) {
  for (let index of numbers.keys()) {
    let res = target - numbers[index]; // 要搜索的值
    for (let i = numbers.length - 1; i > index; i--) {
      // 倒序查找，跳过已经遍历过的值
      if (res === numbers[i]) return [index, i]; // 搜索到了 即找到
    }
  }
};
console.log(twoSum([2, 7, 11, 15], 9), twoSum([2, 33, 11, 2], 4));

indexOf()

indexOf的第二个参数是开始搜索的位置，也可以跳过前面已经搜索过的值。

const twoSum = function(numbers, target) {
  for (let index of numbers.keys()) {
    let res = target - numbers[index]; // 相减
    let search = numbers.indexOf(res, index + 1); // 跳过前面已经搜索过的，防止2+2=4 搜索两个2在同一个位置
    if (search !== -1) {
      return [index, search]; // 直接返回值
    }
  }
};
console.log(twoSum([2, 7, 11, 15], 9), twoSum([2, 33, 11, 2], 4));

鼓励我一下：

觉得还不错的话，给我的点个star吧

中位数

难度：简单

描述：

给定一个未排序的整数数组，找到其中位数。

中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第 N/2 个数。

样例：

给出数组[4, 5, 1, 2, 3]，返回 3

给出数组[7, 9, 4, 5]，返回 5

思路分析：

升序排序数组
模拟几个数组的返回值，找到里面的规律，找出数组中对应元素。

代码模板：

/**
 * @param nums: A list of integers
 * @return: An integer denotes the middle number of the array
 */
const median = function(nums) {};

想一想再看答案

代码：

判断奇数偶数，找到对应的下标

/**
 * @param nums: A list of integers
 * @return: An integer denotes the middle number of the array
 */
const median = function(nums) {
  nums.sort((a, b) => {
    return a - b; // 升序排序
  });
  var num = nums.length; // 保存数组长度
  if (num % 2 !== 0) {
    // 判断奇数偶数
    return nums[(num + 1) / 2 - 1]; // 奇数转偶数
  } else {
    return nums[num / 2 - 1]; // 减一 对应数组下标
  }
};

奇数上舍入，找到下标

两种写法一样，但无疑第二种写法更为优雅。

/**
 * @param nums: A list of integers
 * @return: An integer denotes the middle number of the array
 */
const median = function(nums) {
  nums.sort((v1, v2) => v1 - v2);
  return nums[Math.ceil(nums.length / 2) - 1]; // 
};

鼓励我一下：

觉得还不错的话，给我的点个star吧

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2018-09-30，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 OBKoro1前端进阶积累微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度