数组

概述

数组中的元素在内存中是连续存储的，且每个元素占相同的内存。

冒泡排序

遍历数组，比较相邻两个元素，重复直至排序完成。

function bubbleSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    // 每遍历一次，最大的数就已经最后面了，不需要再比较，所以长度减i
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换位置
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

快速排序

每次选出一个基准值，小于它的放左边，大于它的放右边，重复直至排序完成。

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0];

  let left = [],
    right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

选择排序

每次从待排序数组中选出最小或最大的一个元素，放到已排序的序列的末尾，重复直至排序完成。

function selectSort(arr) {
  let length = arr.length,
    minIndex,
    temp;
  for (let i = 0; i < length - 1; i++) {
    minIndex = i;
    for (let j = i; j < length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

插入排序

选择元素，插入有序数组。

function insertSort(arr) {
  let length = arr.length;
  for (let i = 1; i < length; i++) {
    let temp = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr;
}

快速了几种排序

练习 1：转置矩阵

给定一个矩阵 A， 返回 A 的转置矩阵。

矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：[[1,4,7],[2,5,8],[3,6,9]]

/**
 * @param {number[][]} A
 * @return {number[][]}
 */
var transpose = function(A) {
  let col = A.length,
    row = A[0].length,
    result = [];

  for (let i = 0; i < col; i++) {
    for (let j = 0; j < row; j++) {
      if (!result[j]) {
        result[j] = [];
      }
      result[j].push(A[i][j]);
    }
  }
  return result;
};

练习 2: 主要元素

数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

🌰 1:

输入：[1,2,5,9,5,9,5,5,5]
输出：5

🌰 2:

输入：[3,2]
输出：-1

🌰 3:

输入：[2,2,1,1,1,2,2]
输出：2

解题方法：摩尔投票+验证法

摩尔投票，相同的数++，不同的数--

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  // 首先找到众数
  let major,
    count = 0;
  for (let i = 0; i < nums.length; i++) {
    if (count === 0) {
      major = nums[i];
    }

    if (major === nums[i]) {
      count++;
    } else {
      count--;
    }
  }

  // 计算众数出现的次数
  let sum = 0;
  for (let j = 0; j < nums.length; j++) {
    if (major === nums[j]) {
      sum++;
    }
  }

  return Math.floor(nums.length / 2) < sum ? major : -1;
};

练习 3: 有序数组的平方

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

🌰 1:

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

🌰 2:

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

解题思路：双指针，将最大的塞到最后面去。

/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortedSquares = function(A) {
  let left = 0,
    right = A.length - 1,
    result = [];

  while (left <= right) {
    let start = A[left] * A[left],
      end = A[right] * A[right];
    if (start > end) {
      result.unshift(start);
      left++;
    } else {
      result.unshift(end);
      right--;
    }
  }
  return result;
};

练习 4: 三个数最大的乘积

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

🌰 1:

输入: [1, 2, 3];
输出: 6;

🌰 2:

输入: [1, 2, 3, 4];
输出: 24;

解题思路：先排序。正数，取前三个，负数，取前一后二。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumProduct = function(nums) {
  let len = nums.length;
  nums.sort((a, b) => b - a);
  let max1 = nums[0] * nums[1] * nums[2];
  let max2 = nums[0] * nums[len - 1] * nums[len - 2];
  return max1 > max2 ? max1 : max2;
};

练习 5: 种花问题

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含 0 和 1，其中 0 表示没种植花，1 表示种植了花），和一个数  n 。能否在不打破种植规则的情况下种入  n  朵花？能则返回 True，不能则返回 False。

🌰 1:

输入: (flowerbed = [1, 0, 0, 0, 1]), (n = 1);
输出: True;

解题思路： 前后补 0，解决边界问题 001, 100. 每连续的 3 个 0， 就可以种植一朵花。

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
  flowerbed = [0].concat(flowerbed, [0]);
  let len = flowerbed.length,
    num = 0;
  for (let i = 1; i < len - 1; i++) {
    if (
      flowerbed[i] === 0 &&
      flowerbed[i - 1] === 0 &&
      flowerbed[i + 1] === 0
    ) {
      flowerbed[i] = 1;
      num++;
    }
  }
  return n <= num;
};

练习 6: 汇总区间

给定一个无重复元素的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

"a->b" ，如果 a != b

"a" ，如果 a == b

🌰 1:

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

🌰 2:

输入：nums = []
输出：[]

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function(nums) {
  let start = 0,
    end = 0,
    result = [];
  for (let i = 0; i < nums.length; i++) {
    end = i;
    if (nums[i] + 1 !== nums[i + 1]) {
      if (nums[start] === nums[end]) {
        result.push(`${nums[start]}`);
      } else {
        result.push(`${nums[start]} -> ${nums[end]}`);
      }
      start = end = i + 1;
    }
  }
  return result;
};

练习 7： 存在连续三个奇数的数组

给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false

🌰 1:

输入：arr = [2,6,4,1]
输出：false
解释：不存在连续三个元素都是奇数的情况。

🌰 2:

输入：arr = [1,2,34,3,4,5,7,23,12]
输出：true
解释：存在连续三个元素都是奇数的情况，即 [5,7,23] 。

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var threeConsecutiveOdds = function(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] % 2 === 0) {
      count = 0;
    } else {
      count++;
    }
    if (count >= 3) return true;
  }
  return false;
};

练习 8: 两数之和

给定一个整数数组 nums  和一个目标值 target，请你在该数组中找出和为目标值的那   两个   整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案，不会有其他的数相加也等于目标值。但是，数组中同一个元素不能使用两遍。

🌰:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

function twoSum(nums, target) {
  let result = [];
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        result.push(i, j);
        return result;
      }
    }
  }
}

function twoSum(nums, target) {
  // 用于储存出现过的数字，以及对应的索引
  let obj = {};
  for (let i = 0; i < nums.length; i++) {
    let diff = target - nums[i];
    let diffIdx = obj[diff];
    if (diffIdx !== undefined) {
      return [diffIdx, i];
    } else {
      obj[nums[i]] = i;
    }
  }
}

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