第一天

力扣第912题、56题 排序

912.排序数组

快速排序

推荐

var sortArray = function(nums) {
    if(nums.length <= 1){return nums}
    let pivotIndex = Math.floor(nums.length / 2)
    let pivot = nums.splice(pivotIndex,1)[0]
    let left = []
    let right = []
    for(let i = 0; i < nums.length; i++){
        if(nums[i] < pivot){
            left.push(nums[i])
        }else{
            right.push(nums[i])
        }
    }
    return sortArray(left).concat([pivot],sortArray(right))
};

思路：找个基准，把它单独提出来，把他和剩下的数进行比较，比基准小的放左边，比基准大的放右边，然后左右两边重复此操作，最后把左、基准、右拼起来返回

选择排序

不推荐，容易超时

var sortArray = function(nums) {
  for (let i = 0; i < nums.length; i++) {
      let min = Infinity; //最小数的值
      let minIndex; //最小数的下标
      for (j = i; j < nums.length; j++) {
          if (nums[j] < min) {
              min = nums[j] //更新最小值
              minIndex = j; //更新下标
          }
      }
      [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
        //交换数组中的位置
  }
  return nums;
};

思路：每次找到当前范围的最小值，跟当前循环的i交换位置，也就是放到最前面，然后i++

56.合并区间

排序加贪心

思路：先排序，然后贪心算法。sort()排序好后，把当前区间的左边界和上一个区间的右边界进行比较，如果是上一个区间的有边界大，那么就Math.max()它们的右边界合并区间,如果当前边界的左区间大，就把整个区间push到数组目标数组里面

var merge = function(intervals){
  if(intervals === null || !intervals.length){
    return intervals
  }
  intervals.sort((a,b) => a[0] - b[0])
  const result = []
  result.push(intervals[0])
  for(let i = 1; i < intervals.length; i++){
    if(result[result.length-1][1] < intervals[i][0]){
      result.push(intervals[i])
    }else{
      result[result.length-1][1] = Math.max(
        result[result.length-1][1],
        intervals[i][1]
      )
    }
  }
  return result
}