算法题之数组相关 | GeniusFunny的个人博客

算法题之数组相关

GeniusFunny 11月 20, 2019

算法题之数组相关~~~~

数组中重复的数字

题目

在一个长度为n的数组里的所有数字都在0～n-1的范围内，找出其中重复的数字。

解决方案

先排序后，与后一个元素进行比较

const result = new Set();
for (let i = 0; i < sortedNumbers.length - 1; i++) {
  if (sortedNumbers[i] === sortedNumbers[i+1]) 						   
    result.add(sortedNumbers[i++])
}

新建数组，索引为数组元素，值为数组元素出现的次数：

// 数组：numbers
let numberArray = [];
const result = new Set();
numbers.forEach(item => {
  numberArray[item] = numberArray[item] ? numberArray[item]++ : 1;
  if (numberArray[item] > 1) result.add(item);
})
console.log(result.values())

使用一个哈希表，存储遍历的数字；遍历的时候判断哈希表中是否已有该数字

索引数值对应法

若索引与索引对应的值不一致，则判断与索引对应的值作为的索引指向的值是否相等，若相等则该数字重复，遍历索引+1；若不相等则交换2值，重复此过程直到发现第一个重复的数字

for (let i = 0; i < numbers.length; ) {
  if (numbers[i] === i) {
    i++
    continue;
  } else if (numbers[i] === numbers[numbers[i]]) {
    result.add(numbers[i]);
    i++;
  } else {
    let temp = numbers[i]
    numbers[i] = numbers[temp]
    numbers[temp] = temp;
  }
}

镜像问题

不修改数组找出重复的数字

题目：一个长度为n+1的数组里，所有数字都在1-n范围内，找出数组中任意一个重复的数字，但不能修改输入的数组。

解决方案：

新建数组+判断数字出现的次数>1
哈希表存储，判断数字是否已经存在于哈希表中

中间数字法

中间数字为m，统计1～m、m～n+1两个区间的数字出现的次数
多出现1次的区间再分为2部分，再次统计
循环上过程，直到找到一个重复的数字

function find_repeat_number(numbers) {
  let mid = Math.floor(numbers.length / 2);
  let low = 1;
  let high = numbers.length - 1;

  while (1) {
    let left = 0
    let right = 0
    console.log(`low: ${low}, mid: ${mid}, high: ${high}`)
    for (let i = 0, len = numbers.length; i < len; i++) {
      if (numbers[i] <= mid && numbers[i] >= low) left++;
      else if (numbers[i] > mid && numbers[i] <= high) right++
    }
    if (left > (mid - low + 1)) {
      if (mid === low) return mid;
      high = mid;
      mid = Math.floor((low + high) / 2);
    } else if (right > (high - mid)){
      if (mid + 1 === high) return high;
      low = mid;
      mid = Math.floor((low + high) / 2);
    }
    console.log(`left: ${left}, right: ${right}`)
    left = right = 0
  }
}

数组去重

简单判断相等的方法对NaN无效，因为NaN === NaN为false
ES6的语法：Set，new Set(...arr)；无法去除{}
新开数组+数组排序，相邻元素进行比较；相邻元素不同的扔进新数组
新开数组+includes：同上
原数组：Array.prototype.indexOf + Array.prototype.filter
对象属性法，数组元素的字符串化后的值作为key。【key：typeof 值+ 值】

Array.prototype.reduce + includes

1	arr.reduce((acc, cur, idx, src) => acc.includes(cur) ? acc : acc.push(cur) && acc, [])

双重for循环+Array.prototype.splice

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

递归去重

二维数组中的查找

题目

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序；给一个数组和整数，判断此数是否在数组中。

解决方案

从数组的右上角（左下角也OK）出发：

若相等则返回true
若值大于整数，剔除数字所在列【行索引-1】
若值小于整数，剔除数字所在行【列索引+1】

function findNumber(arr, num) {
  const rows = arr.length;
  const cols = arr[0].length;
  let row = 0;
  let col = cols - 1;
  while(row < rows && row >= 0 && col < cols && col >= 0) {
    console.log(`比较${num} 与 arr[${row}][${col}]: ${arr[row][col]}`)
    if (arr[row][col] < num) {
      row++;
    } else if (arr[row][col] > num) {
      col--;
    } else {
      return true;
    }
  }
  return false;
}

旋转数组的最小数字

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

解决方案

使用二分查找的思维来解决此问题

上半区出现start > mid，最小元素一定出现在此区域
下半区出现mid > end，最小元素一定出现在此区域
mid = start, 说明此区域元素必定都相等，所以可以将start设置为mid
mid = end，元素可能是先升后降，所以将end-1或mid+1

function spinArray(arr) {
  if (!arr && !arr.length) return undefined;
  const len = arr.length;
  if (arr[0] < arr[len-1]) return arr[0];
  if (arr[0] >= arr[len-1]) {
    let start = 0;
    let end = len-1;
    let mid = Math.floor((start + end)/2);
    while(end - start > 0) {
      if(arr[start] > arr[mid] ) {
        // 上半区出现start > mid，最小元素一定出现在此区域
        end = mid;
        mid = Math.floor((start + end) / 2);
        continue;
      }
      if (arr[mid] > arr[end]) {
        // 下半区出现mid > end，最小元素一定出现在此区域
        start = mid+1;
        mid = Math.floor((start + end) / 2);
        continue;
      }
      if (arr[start] === arr[mid]) {
        // mid = start, 说明此区域元素必定都相等，所以可以将start设置为mid
        start = mid;
      }
      if (arr[end] === arr[mid]) {
        // mid = end，元素可能是先升后降，所以将end-1或mid+1
        end -= 1;
      }
      mid = Math.floor((start + end) / 2);
    }
    return arr[start];
  }
}

数组中出现次数超过一半的数字

题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字

解决方案

解决方案（一）：哈希表大法，时间O(n)、空间O(n)

新建一个哈希表存储数字出现的次数
添加数字出现次数时与数组长度一半进行比较，若已超过一半直接返回，否则继续遍历

function find(arr) {
  const len = arr.length;
  const times = new Map();
  for(let i = 0; i < len; i++) {
    let currentNumberTimes = times.get(arr[i]) || 0;
    times.set(arr[i], currentNumberTimes++);
    if ((currentNumberTimes+1) * 2 > len) return arr[i]
  }
}

解决方案（二）：基于Partition函数的时间复杂度为O(n)的算法
- 中位数即是出现超过一半的数字
- 随机选择一个元素，然后调整数字的顺序，比它小的在左边，比它大的在右边
  - 调整后，判断此数字下标
    - 若小于n/2，则中位数在它右边
    - 若大于n/2，则中位数在它左边
    - 若等于n/2，则其就是中位数

统计数字出现的次数

遍历数组，统计数字出现的次数，若下一个数字与其不同次数-1，相同+1
次数为0时，改为统计下一个数字的次数

遍历到最后，始终有一个数字的次数大于1，该数字就是所求数字

function moreThanHalfNumber(arr) {
  if (!arr.length) return;
  let count = 0;
  let currentNumber = arr[0];
  const len = arr.length;
  for(let i = 0; i < len; i++) {
    if (arr[i] === currentNumber) count++
    else {
      count--
      if (count === 0) {
        currentNumber = arr[i];
        count++;
      }
    }
  }
  return currentNumber;
}

连续子数组的最大和

题目

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

解决方案

解决方案一：数字累加判断法

遍历数组，不断累加数字，更新sum、maxSum

若加上当前数字后值为负值，则说明后面序列的数字不需要前面的数字序列，sum = 当前数字
- 若当前数字为负值，则sum = 下一个数字
每执行一次循环比较一次sum与maxSum的大小，作出更新

function findGreatestSumOfSubArray(arr) {
  const len = arr.length;
  let sum = 0;
  let maxSum = Number.MIN_SAFE_INTEGER;
  for(let i = 0; i < len; i++) {
    if(sum <= 0) sum = arr[i];
    else
      sum += arr[i]
    if (sum > maxSum) maxSum = sum;
  }
  return maxSum
}

解决方案二：DP

f(i) : 以第i个数字结尾的子数组最大值

f(i) 的值应该为：

当i=0或者f(i-1) <=0 : f(i) = data[i]
当i不等于0且f(i-1) > 0: f(i) = data[i] + f(i-1)

function findGreatestSumOfSubArrayDP(arr) {
  const len = arr.length;
  let dp = [];
  dp[0] = arr[0]
  let max = Number.MIN_SAFE_INTEGER;
  for(let i = 1; i < len; i++) {
    dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
    max = Math.max(max, dp[i]);
  }
  return max;
}

从数组中选出N个数使其和等于M

题目

从数组中选出N个数使其和等于M，一共有多少种选法

解决方案

二进制法

function search(arr, count, sum) {
  var len = arr.length, res = [];
  for (var i = 0; i < Math.pow(2, len); i++) {
    if (n(i) == count) {
      var s = 0, temp = [];
      for (var j = 0; j < len; j++) {
        if (i & 1 << (j)) {
          s += arr[j]
          temp.push(arr[j])
        }
      }
      if (s == sum) {
        res.push(temp)
      }
    }
  }
  return res;
}

function n(i) {
  var count = 0;
  while (i) {
    if (i & 1) {
      ++count;
    }
    i >>= 1;
  }
  return count;
}

递归法

function search(arr, n, m) { 
  if(n === 0) return m === 0 ? [[]] : []; 
  if(arr.length < n) return [];  
  return search(arr.slice(1), n-1, m - arr[0]) 
    .map(so => [arr[0], ...so]) 
    .concat(search(arr.slice(1), n, m)); 
}

数组中的逆序对

题目

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

解决方案

暴力法：O(n^2)

归并统计法

将数组分为2个子数组，分别统计子数组的逆序对，然后再统计两个子数组间的的逆序对。

function inversePairs(data) {
  function mergeSort(arr, left, right, temp) {
    if (left < right) {
      let mid = Math.floor((left + right) / 2);
      let r = mergeSort(arr, left, mid, temp);
      let l = mergeSort(arr, mid + 1, right, temp);
      let m = merge(arr, left, mid, right, temp);
      return r+m+l;
    } else {
      return 0;
    }
  }
  function merge(arr, left, mid, right, temp) {
    let i = mid;
    let j = right;
    let tempIndex = right;
    let count = 0;
    while(i >= left && j > mid) {
      if(arr[i] > arr[j]) {
        count += (j-mid);
        temp[tempIndex--] = arr[i--] 
      } else {
        temp[tempIndex--] = arr[j--]
      }
    }
    while(i >= left) temp[tempIndex--] = arr[i--]
    while(j > mid) temp[tempIndex--] = arr[j--]
    for(let i = left; i <= right; i++) {
      arr[i] = temp[i];
    }
    return count;
   }
  return mergeSort(data, 0, data.length - 1, [])
}