常见数组算法

[Leo-lin214]

对数组数据结构常见的算法进行总结，也为了更好滴应对后面深入学习算法。

把数组排成最小的树

输入一个正整数数组，把数组里所有的数字拼起来排成一个数，然后输出拼接后的所有数字里面最小的一个。

答案

  const getMinNum = nums => {
    if (!nums || nums.length === 0) return '';
    return nums.sort(compare).join('');
  }
  const compare = (a, b) => {
    const front = `${a}${b}`;
    const behind = `${b}${a}`;
    return front - behind;
  }
  

第一个只出现一次的字符

在一个字符串中找到第一个只出现一次的字符，并返回它的位置，如果没有就直接返回 -1。

答案

  // 时间复杂度：O(n),  空间复杂度：O(n)
  const getOneStr1 = str => {
    if (!str) return -1;
    const map = {};
    for (let i = 0; i < str.length; i++) {
      if (map[str[i]]) map[str[i]] = map[str[i]] + 1;
      else map[str[i]] = 1;
    }
    for (let i = 0; i < str.lenth; i++) {
      if (map[str[i]] === 1) return i;
    }
    return -1;
  }
// 时间复杂度：O(n^2)，空间复杂度：O(0)

const getOneStr2 = str => {

if (!str) return -1;

for (let i = 0; i < str.length; i++) {

if (str.indexOf(str[i]) === str.lastIndexOf(str[i])) return i;

}

return -1;

}

调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数都在偶数前面。

答案

  const changeArr = arr => {
    let start = 0;
    let end = arr.length - 1;
    while (start < end) {
      while (arr[start] % 2 === 1) start++;
      while (arr[end] % 2 === 0) end--;
      if (start < end) {
        [arr[start], arr[end]] = [arr[end], arr[start]];
      }
    }
    return arr;
  }
  

构建乘积数组

给定一个数组 A [0, 1, ..., n - 1]，请构建一个数组 B [0, 1, ..., n - 1]，其中 B 中的元素，B[i] = A[0] * A[1] * ... * A[i - 1] * A[i + 1] * ... * A[n - 1]。

答案

  const createChenArr = arr => {
    if (Array.isArray(arr) && arr.length) {
      const leftArr = new Array(arr.length).fill(0);
      const rightArr = new Array(arr.length).fill(0);
      for (let i = 0; i < arr.length; i++) leftArr[i] = i === 0 ? 1 : leftArr[i - 1] * arr[i - 1];
      for (let i = arr.length - 1; i >= 0; i--) rightArr[i] = i === arr.length - 1 ? 1 : rightArr[i + 1] * arr[i + 1];
      const result = [];
      for (let i = 0; i < arr.length; i++) {
        if (i === 0) {
          result[i] = rightArr[0];
        } else if (i === arr.length - 1) {
          result[i] = leftArr[i];
        } else {
          result[i] = leftArr[i - 1] * rightArr[i + 1];
        }
      }
      return result;
    }
    return arr;
  }
  

和为S的连续正整数序列

输入一个正数 S，打印出所有和为 S 的连续正数序列。

例如：输入 15，有序序列有 [1, 2, 3, 4, 5]、[4, 5, 6]、[7, 8]。

答案

  const getContinueArr = target => {
    const result = [];
    const temp = [1, 2];
    let start = 1;
    let end = 2;
    let sum = 3;
    while (end < target) {
      while (sum < target && end < target) {
        temp.push(++end);
        sum += end;
      }
      while (sum > target && start < end) {
        temp.shift();
        sum -= start++;
      }
      if (sum === target && temp.length) {
        result.push([...temp]);
        temp.push(++end);
        sum += end;
      }
    }
    return result;
  }
  

和为S的两个数字

输入一个递增排序的数组和一个数字 S，在数组中查找两个数，使得它们的和正好是 S，如果有多对数字的和等于 S，输出两个数的乘积最小的。

答案

  const getMinSum = (arr, target) => {
    if (Array.isArray(arr) && arr.length) {
      let start = 0;
      let end = arr.length - 1;
      while (start < end) {
        const sum = arr[start] + arr[end];
        if (sum === target) {
          return [arr[start], arr[end]];
        } else if (sum > target) {
          end--;
        } else {
          start++;
        }
      }
    }
    return [];
  }
  

连续子数组的最大和

输入一个整形数组，数组里面有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值，要求时间复杂度为 O(n)。

例如，{6, -3, -2, 7, -15, 1, 2, 2}，连续子数组的最大和为8（从第0个开始，到第3个为止）。

答案

  var maxSubArray = function(nums) {
    if (!nums.length) return 0
    let sum = nums[0]
    let result = nums[0]
    for (let i = 1; i < nums.length; i++) {
      if (sum < 0) {
        sum = nums[i]
      } else {
        sum += nums[i]
      }
      result = Math.max(sum, result)
    }
    return result
  };
  

两数之和

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

答案

  const getTwoSum = (nums, target) => {
    const map = {};
    if (Array.isArray(nums)) {
      for (let i = 0; i < nums.length; i++) {
        const diff = target - nums[i];
        if (map[diff]) return [map[nums[i]], map[diff]];
        map[nums[i]] = i;
      }
      return [];
    }
  }
  

扑克牌顺子

扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。

其中 2 - 10为数字本身，A 为 1，J 为 11 ... 大小王可以看成任何数字，可以把它当作 0 处理。

答案

  const getThreeArr = nums => {
    const result = [];
    if (Array.isArray(nums) && nums.length) {
      const numsArr = nums.sort((a, b) => a - b);
      for (let i = 0; i < numsArr.length; i++) {
        if (i && numsArr[i] === nums[i - 1]) continue;
        let left = i + 1;
        let right = numsArr.length - 1;
        while (left < right) {
          const sum = numsArr[i] + numsArr[left] + numsArr[right];
          if (sum === 0) {
            result.push([numsArr[i], numsArr[left], numsArr[right]]);
          }
          if (sum <= 0) {
            while (numsArr[left] === nums[left + 1]) left++; 
          } else {
            while (numsArr[right] === nums[right - 1]) right--; 
          }
        }
      }
    }
    return result;
  }
  

三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素a，b，c，使得 a + b + c = 0？找出所有满足条件且不重复的三元组。

答案

  const isSmooth = arr => {
    if (Array.isArray(arr) && arr.length) {
      let max = 0;
      let min = 14;
      for (let i = 0; i < arr.length; i++) {
        if (arr[i] === 0) continue;
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    return max > min ? (max - min < 5) : false;
  }
  

数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组，求出这个数组中的逆序对的总数 P。

答案

  let count = 0;
  const mergeSort = nums => {
    if (!nums || !nums.length) return nums;
    const mid = parseInt((nums.length - 1) / 2);
    const leftArr = nums.slice(0, mid + 1);
    const rightArr = nums.slice(mid + 1, nums.length);
    return merge(mergeSort(leftArr), mergeSort(rightArr)); 
  }
  const merge = (leftArr, rightArr) => {
    let left = 0;
    let right = 0;
    const result = [];
    while (left < leftArr.length && right < rightArr.length) {
      if (leftArr[left] > rightArr[right]) {
        count += rightArr.length - right;
        result.push(rightArr[right++]);
      } else {
        result.push(leftArr[left++]);
      }
    }
    while (left < leftArr.length) result.push(leftArr[left++]);
    while (right < rightArr.length) result.push(rightArr[right++]);
    return result;
  }
  

顺时针打印矩阵

输入一个矩阵，按照从外向里顺时针的顺序依次打印出每一个数字。

例子：输入如下 4 x 4 矩阵

1 2 3 4

5 6 7 8

9 10 11 12

打印出数字为：1，2，3，4，5，6，7，8，9，10，11，12。

答案

  const logNumber = nums => {
    if (!nums || !nums.length) return nums;
    const row = nums.length;
    const col = nums[0].length;
    const result = [];
    let left = 0;
    let right = col - 1;
    let top = 0;
    let bottom = row - 1;
    let index = 1;
    while (index < row * col) {
      for (let i = left; i <= right; i++) {
        result.push(nums[top][i]);
        index++;
      }
      top++;
      for (let i = top; i <= bottom; i++) {
        result.push(nums[i][right]);
        index++;
      }
      right--;
      for (let i = right; i >= left; i--) {
        result.push(nums[bottom][i]);
        index++;
      }
      bottom--;
      for (let i = bottom; i >= top; i--) {
        result.push(nums[i][left]);
        index++;
      }
      left++;
    }
    return result;
  }
  

四数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在四个元素 a，b，c，d，使得 a + b + c + d = 0。找出所有满足条件且不重复的四元组。

答案

  const getFourSum = (nums, target) => {
    if (!nums || nums.length < 4) return [];
    const result = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length - 3; i++) {
      if (i && nums[i] === nums[i - 1]) continue;
      if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
      for (let j = i + 1; j < nums.length - 2; j++) {
        if (j > i + 1 && nums[j] === nums[j - 1]) continue;
        let left = j + 1;
        let right = nums.length - 1;
        while (left < right) {
          const sum = nums[i] + nums[j] + nums[left] + nums[right];
          if (sum === target) {
            result.push([nums[i], nums[j], nums[left], nums[right]]);
          }
          if (sum <= target) {
            while (nums[left] === nums[++left]); 
          } else {
            while (nums[right] === nums[--right]);
          }
        }
      }
    }
    return result;
  }
  

在排序数组中查找数字

统计一个数字在排序数组中出现的次数。

答案

  const findAmount = (nums, target) => {
    if (!nums || !nums.length) return -1;
    let start = 0;
    let end = nums.length - 1;
    let left = -1;
    let right = -1;
    while (start < end) {
      const mid = parseInt((start + end) / 2);
      if (nums[mid] === target) {
        left = mid;
        end = mid - 1;
      } else if (nums[mid] > target) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }
    start = 0;
    end = nums.length - 1;
    while (start < end) {
      const mid = parseInt((start + end) / 2);
      if (nums[mid] === target) {
        right = mid;
        left = mid + 1;
      } else if (nums[mid] > target) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }
    return (left !== -1 && right !== -1 && left < right) ? right - left + 1 : -1;
  }