数组相关算法

[zhanhongtao]

• 求和, 递归写法
• 求最大值和最小值
• 求第 K 大/小值
• 求数组中出现次数超过一半的元素
• 求数组中元素的最短距离, 即 abs(x - y) 值最小
• 求两个有序数组的共同元素
• 求出现奇数次的元素
• 求数组中满足给定和的数对
• 求最大子段和
• 求最大子段积
• 数组循环移位
• 字符串逆转
• 合并两个有序数组
• 数组重排问题
• 求绝对值最小的元素
• 求组合问题、全排列
• 找左边比自己小, 右边比自己大的元素.
• 找出元素, 它比左边的元素都大, 比右边元素都小.;
• 约瑟夫斯问题
• 找出出现次数刚好是一半的数字

[zhanhongtao]

求和

function sum( array ) {
  return array.reduce(function( base, item ) {
    return base + item;
  });
}

function sum2( array, n ) {
  return n <= 0 ? 0 : array[ n - 1 ] + sum2( array, n - 1 );
}

function sum3( array, i ) {
  if ( i === array.length ) return 0;
  return array[i] + sum3( array, i + 1 );
}

[zhanhongtao]

求最大值和最小值

function max( array ) {
  return array.reduce(function( base, item ) {
    return base > item ? base : item;
  });
}

function min( array ) {
  return array.reduce(function( base, item ) {
    return base > item ? item : base;
  });
}

[zhanhongtao]

求第 K 大值.

// 求最大值, 次大值以及第 k 大值.
// 思路: 使用前 k 个元素创建大顶堆. 调整大顶堆.
function getLeftChild( i ) {
  return 2 * i;
}

function getRightChild( i ) {
  return 2 * i + 1;
}

function swap( array, i, j ) {
  var tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
}

function heapAdjust( array, i, n ) {
  var l = getLeftChild( i );
  var r = getRightChild( i );
  var largest = i;
  if ( l < n && array[i] > array[l] ) {
    largest = l;
  }
  else if ( r < n && array[i] > array[r] ) {
    largest = r;
  }
  if ( largest !== i ) {
    swap( array, i, largest );
    heapAdjust( array, largest, n );
  }
}

function createHeap( array, n ) {
  var i = Math.floor( n / 2 );
  for ( ; i >= 0; i-- ) {
    heapAdjust( array, i, n );
  }
}

function findK( array, k ) {
  k = k < 1 ? 1 : k ;
  createHeap( array, k );
  for ( var i = k, l = array.length; i < l; i++ ) {
    if ( array[i] > array[0] ) {
      swap( array, i, 0 );
      createHeap( array, k );
    }
  }
  return array[0];
}

[zhanhongtao]

求数组中出现次数超过一半的元素

function findHalf( array ) {
  var length = array.length;
  if ( array.length === 0 ) return;
  var value;
  var n = 0;
  var i = 0;
  while ( i < length ) {
    if ( value == null ) {
      value = array[i];
      n = 1;
    }
    else if ( value === array[i] ) {
      n++;
    }
    else {
      n--;
      if ( n <= 0 ) {
        value = null;
        n = 0;
      }
    }
    i++;
  }
  return value;
}

[zhanhongtao]

求数组中元素的最短距离, 即 abs(x - y) 值最小

function findMinDistance( array ) {
  array.sort();
  var ret = Math.abs( array[1] - array[0] );
  var length = array.length;
  var i = 2;
  while ( i < length ) {
    var cur = Math.abs( array[i] - array[i-1] );
    ret = ret > cur ? cur : ret;
    i++;
  }
  return ret;
}

[zhanhongtao]

求两个有序数组的共同元素

/**
  给定两个含有n个元素的有序（非降序）整型数组a和b，求出其共同元素，比如
  a = 0, 1, 2, 3, 4
  b = 1, 3, 5, 7, 9
  输出 1, 3
*/
function findSame( a, b ) {
  var ai = 0;
  var bi = 0;
  var al = a.length;
  var bl = b.length;
  var ret = [], j = 0;
  while (1) {
    if ( ai === al || bi === bl ) break;
    if ( a[ai] > b[bi] ) {
      bi++;
    }
    else if ( a[ai] < b[bi] ) {
      ai++;
    }
    else {
      ret[j++] = a[ai];
      ai++;
      bi++;
    }
  }
  return ret;
}

[zhanhongtao]

求出现唯一奇数次的元素

// 找出出现奇数次的元素
function findOddNumber( array ) {
  return array.reduce(function( base, item ) {
    return base ^ item;
  });
}

[zhanhongtao]

求数组中满足给定和的数对

function find( array, n ) {
  array.sort(function( a, b ) {
    return a - b;
  }); // 或者已排序
  var i = 0, j = array.length - 1;
  var ret = [];
  while ( i < j ) {
    var sum = array[i] + array[j];
    if ( sum > n ) {
      j--;
    }
    else if( sum < n ) {
      i++;
    }
    else {
      ret.push( [array[i++], array[j--] ]);
    }
  }
  return ret;
}

[zhanhongtao]

最大子段和

// 给定一个整型数组a，求出最大连续子段之和，如果和为负数，则按0计算，比如1， 2， -5， 6， 8则输出6 + 8 = 14
function findMaxSub( array ) {
  var max = array[0];
  var length = array.length;
  var cur = array[0];
  var i = 1;
  while ( i < length ) {
    cur = cur + array[i];
    if ( cur > 0 ) {
      max = max > cur ? max : cur;
    }
    else {
      max = max > cur ? max : cur;
      cur = 0;
    }
    i++;
  }
  return max;
}

[zhanhongtao]

字符串逆序

// 字符串逆序
// 给定一个含有n个元素的字符数组a，将其原地逆序。
function reverse( string ) {
  var i = 0, j = string.length - 1;
  var array = [];
  while ( i <= j ) {
    array[i] = string[j];
    array[j] = string[i];
    i++;
    j--;
  }
  return array.join('');
}

[zhanhongtao]

合并两个有序数组

function merge( a, b ) {
  var m = a.length, n = b.length;
  var ai = 0, bi = 0;
  var ret = [], i = 0;
  while ( ai < m && bi < n ) {
    if ( a[ai] >= b[bi] ) {
      ret[i++] = b[bi++];
    }
    else {
      ret[i++] = a[ai++];
    }
  }
  if ( ai === m ) {
    while ( bi < n ) {
      ret[i++] = b[bi++];
    }
  }
  else if ( bi === n ) {
    while( ai < m ) {
      ret[i++] = a[ai++];
    }
  }
  return ret;
}

[zhanhongtao]

重新排列

给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：

1. 排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变
2. 不能使用额外存储空间
   例子如下
   输入 0, 3, 0, 2, 1, 0, 0
   输出 0, 0, 0, 0, 3, 2, 1

function reSort( array ) {
  var i = array.length - 1;
  while ( i > 0 ) {
    if ( array[i] === 0 ) {
      var tmp = array[i];
      for( j = i - 1; j >= 0; j-- ) {
        if ( array[j] !== 0 ) {
          array[i] = array[j];
          array[j] = tmp;
          break;
        }
      }
    }
    i--;
  }
}

[zhanhongtao]

找出绝对值最小的元素

function findAbsMin( array ) {
  return array.reduce(function( base, item ) {
    var y = Math.abs( item );
    var x = Math.abs( base );
    return x < y ? x : y;
  });
}

// array 有顺序
// [ -8, -5, -1, 2, 4, 10 ] --> 1;
function findAbsMin2( array ) {
  var l = 0;
  var h = array.length;
  var ret = Math.abs( array[l++] );
  while ( l < h ) {
    if ( array[l] >= 0 ) {
      ret = ret > array[l] ? array[l] : ret;
      break;
    }
    else {
      var item = Math.abs( array[l] );
      ret = ret > item ? item : ret;
    }
    l++;
  }
  return ret;
}

[zhanhongtao]

找左边比自己小, 右边比自己大的元素.

function find( array ) {
  var ret = [], j = 0, l = array.length - 1;
  for ( var i = 1; i < l; i++ ) {
    var c = array[ i ], p = array[ i - 1 ], n = array[ i + 1 ];
    if ( p < c && c < n ) ret[j++] = c;
    if ( n <= c ) i++;
  }
  return ret;
}

[zhanhongtao]

找出元素, 它比左边的元素都大, 比右边元素都小.

一个 int 数组，里面数据无任何限制，要求求出所有这样的数a[i]，
其左边的数都小于等于它，右边的数都大于等于它。
能否只用一个额外数组和少量其它空间实现。

function find( array ) {
  var min = [];
  var max = array[0];
  var mi = 0;
  for ( var i = 1, l = array.length - 1; i < l; i++ ) {
    var c = array[i];
    if ( c > max ) {
      min[mi++] = c;
      max = c;
    }
    else {
      for ( var j = min.length; j >= 0; j-- ) {
        if ( c <= min[j] ) {
          min.pop();
          mi--;
        }
      }
    }
  }
  return min;
}

[zhanhongtao]

全排列.

function swap( array, i, j ) {
  var tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
}

function print( value ) {
  console.log( value );
  console.count( 'print' );
}

function fullPermutation( array, n ) {
  if ( n === 1 ) return print( array );
  // 交换当前元素和最后一个元素, 再处理 xxxx, 最后再交换回去. (*)
  for ( var i = 0; i < n; i++ ) {
    swap( array, i, n - 1 );
    arguments.callee( array, n - 1 );
    swap( array, i, n - 1 );
  }
}

[zhanhongtao]

约瑟夫斯问题

#184

function josephus( array, k, index ) {
  var length = array.length;
  var n = length;
  var index = Math.abs( index ) % length;
  var r = [];
  var hash = []; // 借助 hash!
  var count = 1;
  while ( 1 ) {
    if ( n < 2 ) break; // 杀到只剩下最后一个.
    while ( hash[index] ) {
      index = ++index === length ? 0 : index;
    }
    if ( count === k ) {
      count = 0;
      hash[index] = 1;
      r.push( array[index] );
      n--;
    }
    index = ++index >= length ? 0 : index;
    count++;
  }
  return r; // 返回有序表.
}

[zhanhongtao]

找出出现次数刚好是一半的数字

function get( array ) {
  if ( array.length === 0 ) return null;
  else if ( array.length === 1 ) return array[0];
  else if ( array.length === 2 ) {
    if ( array[0] === array[1] ) return array[0];
    else return null;
  }
  var c1, c2, t1 = 0, t2 = 0;
  for ( var i = 0, l = array.length; i < l; i++ ) {
    if ( t1 === 0 ) {
      c1 = array[i];
      t1 = 1;
    }
    else if ( t2 === 0 && c1 !== array[i] ) {
      c2 = array[i];
      t2 = 1;
    }
    else {
      if ( c1 === array[i] ) {
        t1++;
      }
      else if ( c2 === array[i] ) {
        t2++;
      }
      else { 
        t1--;
        t2--;
      }
    }
  }
  return t1 > t2 ? c1 : c2;
}

// get( [0, 1, 0, 2] );