学习笔记-JavaScript数组编程题

1.给定一个整数数组, 找到从三个整数中产生的最大乘积
示例:

const unsortedArray = [-10, 7, 29, 30, 5, -10, -70];
computeProduct(unsortedArray); // 21000

解答:

function sortIntegers(a, b) {
  return a - b;
}

function computeProduct(unsorted) {
  const sortedArray = unsorted.sort(sortIntegers);
  const array_n_element = sortedArray.length - 1;

  let product1 = 1;
  let product2 = 1;

  for (let x = array_n_element; x > array_n_element - 3; x--) {
    product1 = product1 * sortedArray[x];
  }

  product2 = sortedArray[0] * sortedArray[1] * sortedArray[array_n_element];

  if (product1 > product2) return product1;

  return product2;
}

2. 一个未排序的数组包含 n 个连续数字中的（n-1）个数字，找到缺失的数字，要求时间复杂度为 O(n)
示例：

const arrayOfIntegers = [2, 5, 1, 4, 9, 6, 3, 7];
const upperBound = 9;
const lowerBound = 1;

findMissingNumber(arrayOfIntegers, upperBound, lowerBound); // 8

解答：

function findMissingNumber(arrayOfIntegers, upperBound, lowerBound) {
  let sumOfIntegers = 0;
  for (let i = 0; i < arrayOfIntegers.length; i++) {
    sumOfIntegers += arrayOfIntegers[i]; // 得到数组的和(不包含缺失数字)
  }

  upperLimitSum = (upperBound * (upperBound + 1)) / 2; // (n*(n+1))/2得到1到n的和
  lowerLimitSum = (lowerBound * (lowerBound - 1)) / 2; // 得到1到最小数字的和

  theoreticalSum = upperLimitSum - lowerLimitSum; // 得到最小数字到n的和

  return theoreticalSum - sumOfIntegers;
}

3. 数组去重
示例：

const array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];

uniqueArray(array); // [1, 2, 3, 5, 9, 8]

解答：

// ES6
Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8]

// ES5
function uniqueArray(array) {
  const hashmap = {};
  const unique = [];

  for(let i = 0; i < array.length; i++) {
    if(!hashmap.hasOwnProperty(array[i])) {
      hashmap[array[i]] = 1;
      unique.push(array[i]);
    }
  }

  return unique;
}

4. 给定一个整数数组，请找出两个元素之间的最大差，较小值的元素必须位于较大元素之前
示例：

const array = [7, 8, 4, 9, 9, 15, 3, 1, 10];

findLargestDifference(array); // 11  4 和 15

解答：

function findLargestDifference(array) {
  if (array.length <= 1) return -1;
  let currentMin = array[0];
  let currentMaxDifference = 0;
  
  for (let i = 1; i < array.length; i++) {
    if (array[i] > currentMin && (array[i] - currentMin > currentMaxDifference)) {
      currentMaxDifference = array[i] - currentMin;
    } else if (array[i] <= currentMin) {
      currentMin = array[i];
    }
  }

  if (currentMaxDifference <= 0) return -1;

  return currentMaxDifference;
}

5. 给定一个整数数组，返回一个数组，其中 output [i] 等于自身以外的所有元素的乘积，要求时间复杂度为 O(n)
示例：

const firstArray = [2, 2, 4, 1];
const secondArray = [0, 0, 0, 2];
const thirdArray = [-2, -2, -3, 2];

productExceptSelf(firstArray); // [8, 8, 4, 16]
productExceptSelf(secondArray); // [0, 0, 0, 0]
productExceptSelf(thirdArray); // [12, 12, 8, -12]

解答：

function productExceptSelf(numArray) {
  let product = 1;
  const size = numArray.length;
  const output = [];

  for (let x = 0; x < size; x++) {
    output.push(product);
    product = product * numArray[x];
  }

  let product2 = 1;
  for (let i = size - 1; i > -1; i--) {
    output[i] = output[i] * product2;
    product2 = product2 * numArray[i];
  }

  return output;
}

6. 求两个数组的交集
示例：

const firstArray = [2, 2, 4, 1];
const secondArray = [1, 2, 0, 2];

intersection(firstArray, secondArray); // [2, 1]

解答：

function intersection(firstArray, secondArray) {
  const hashmap = {};
  const intersectionArray = [];

  firstArray.forEach(element => {
    hashmap[element] = 1;
  });

  secondArray.forEach(element => {
    if (hashmap[element] === 1) {
      intersectionArray.push(element);
      hashmap[element]++;
    }
  });

  return intersectionArray;
}