By

文章目录
  1. 1. 小范围排序练习题
  2. 2. 重复值判断练习题
  3. 3. 荷兰国旗问题
  4. 4. 有序矩阵查找练习题
  5. 5. 最短子数组
  6. 6. 相邻两数最大差值练习题

与排序有关的问题。 我发现在掌握了排序算法后，想到这些题目的思想也不难，而且实现也多是可以借鉴经典的排序算法的。 ^_^

小范围排序练习题

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

思想：

因为k值比较小所以可以使用插入排序，时间复杂度是O(N*k)。 冒泡、选择、快排和归并排序和原始顺序无关。

此题最好的方法是改进的堆排序。依次对k个数做小根堆，依次取出第1个数。 调整小根堆时间复杂度是O(lgK)，需要调整N次，整体时间复杂度是O( N* lgk)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
function limitedExtendSort(arr,k){
  if(arr == null || arr.length ==0 ||k==0){
      return 
  }
  var heap = getKheap(arr,k)  
  for(var i=k;i<arr.length;i++){
     arr[i-k] = heap[0]
     heap[0] = arr[i]
     heapify(heap,0,k)
  }
  for(var i=arr.length-k;i<arr.length;i++){
      arr[i] = heap[0];
      [heap[0],heap[k-1]]=[heap[k-1],heap[0]];
      heapify(heap,0,--k)
  }
}
function getKheap(arr,k) {
    var heap=[]
    for(var i=0;i<k;i++){
        heapInsert(heap,arr[i],i)
    }
return heap 
}
// 因为只需要保证在堆顶的位置是最小值，所以不用完全建成堆，这样省时
function heapInsert(heap,value,index){
    heap[index] = value
    while(index!=0){
        var parent = Math.floor((index-1)/2)
        if(heap[parent] > heap[index]){
            [heap[parent],heap[index]] = [heap[index],heap[parent]];
            index = parent 
        }else{
            break
        }
    }
}
function heapify(arr,start,heapSize){
    var left = start*2+1
    var right = start*2+2 
    var min = start 
    while(left< heapSize){
        if(arr[left]<arr[min]){
            min = left
        }
        if(right<heapSize && arr[right]<arr[start]){
            min = right 
        }
        if(min != start){
            [arr[start],arr[min]] = [arr[min],arr[start]];
            start = min 
            left = start*2+1
            right = start*2 +2
        }else{
            break;
        }
    }
}

重复值判断练习题

判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。
给定一个int数组A及它的大小n，请返回它是否有重复值。

思想：

判断是否有重复值，可以先进行排序，然后遍历一遍。题目要求使用空间复杂度是O(1)，考虑空间复杂度为o(1)的排序有冒泡、插入、选择、希尔、和堆排序。

这个问题最好的方法是非递归实现的堆排序。 当递归实现堆排序时空间复杂度是O(logn)非递归的调整堆的过程如下：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function maxheapify(arr,start,heapSize){
    var largest = start,left,right
    while(start<=heapSize){
        left = 2*start+1
        right = 2*start+2
        if(arr[start]<arr[left]&& left<=heapSize){
            largest = left
        }
        if(arr[right]>arr[largest] && right<=heapSize){
            largest = right
        }
        if(largest!==start){
            [arr[largest],arr[start]] = [arr[start],arr[largest]]
            start = largest
        }else{
            start = heapSize+1
        }
    }
}

荷兰国旗问题

有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。

思想：

这个问题类似于快排，可以使用快排中的partition 方法，在 数组左边建立一个空数组进行放0，在数组右边建立空数组放2，当中间索引遇到右边的数组时就停止。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function HollandFlag(arr){
    var left = -1,right = arr.length
    for(var i=0;i<right;i++){
        if(arr[i] === 0){
            left++
            [arr[i],arr[left]]=[arr[left],arr[i]]
        }else if(arr[i] ===2){
            right--
            [arr[i],arr[right]] =[arr[right],arr[i]]
            i--
        }
    }
    return arr
}

有序矩阵查找练习题

现在有一个行和列都排好序的矩阵，请设计一个高效算法，快速查找矩阵中是否含有值x。
给定一个int矩阵mat，同时给定矩阵大小nxm及待查找的数x，请返回一个bool值，代表矩阵中是否存在x。所有矩阵中数字及x均为int范围内整数。保证n和m均小于等于1000。

思想：

从矩阵的右上角开始比较，这样的最快的时间复杂度是O(m+n)，空间复杂度是o(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
function findFromArray(arr,m,n,num) {
  for(var i=0;i<m;i++){
    for(var j=n-1;j>=0;j--){
        if(arr[i][j]<num){
           break;
        }
        if(arr[i][j]==num){
            return true
        }
    }      
  } 
return false
}

最短子数组

对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。
给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的长度。(原序列位置从0开始标号,若原序列有序，返回0)。保证A中元素均为正整数。

思想：

先从左向右遍历，记录已遍历过的最大数值比当前遍历数值要大的最右边的位置 right
然后再从右向左遍历，记录已遍历过的最小数值比当前遍历数值要小的最左边的位置 left
那么位置之差就是需要排序的最短子数组
这样的最快的时间复杂度是O(n)，空间复杂度是o(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function subSequence(arr) {
  var max = arr[0],min = arr[arr.length-1]
  var right =0 ,left = arr.length-1
  for(var i=0;i<arr.length;i++){
      if(max <arr[i]){
          max = arr[i]
      }
      if(max>arr[i]){
          right =i
      }
  }
  for(var i=arr.length-1;i>=0;i--){
      if(min >arr[i] ){
          min = arr[i]
      }
      if(min<arr[i]){
          left = i
      }
  }
  if(left ===right) {
      return 0
  }else{
      return right-left+1
  }
}

相邻两数最大差值练习题

有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。
给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个

思想：

利用桶排序的思想，共建立（n+1）个桶，将最大的数值放在最后一个桶中，其余的数值均分分布n个桶中，因为共有n+1个桶n个数，所以会出现空桶，相邻的两个数的最大差值不可能出现在同一个桶中，只会出现的空桶附近。

时间复杂度是O(n)，空间复杂度是o(n)
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function gap(arr){
  var min = arr[0],max = arr[0]
  for(var i=0;i<arr.length;i++){
      if(min>arr[i]){
          min = arr[i]
      }
      if(max< arr[i]){
          max = arr[i]
      }
  }
  var hasNums=[],maxs=[],mins=[]
  for(var i=0;i<arr.length;i++){
      var index = getBucketIndex(arr[i],arr.length,min,max)  // 得到对应桶的序号
      maxs[index] = hasNums[index]?Math.max(maxs[index],arr[i]):arr[i] // 记录桶中的最值
      mins[index] = hasNums[index]?Math.min(mins[index],arr[i]):arr[i]
      hasNums[index] = true
  }
  maxs[arr.length] = mins[arr.length] = max
 var i=0,res=0,firstMax=0;
 while(i<=arr.length){
     if(hasNums[i++]){
       firstMax = maxs[i-1];  // 第一个非空桶的最大值
       break;
     }
 }
 for(;i<=arr.length;i++){
     if(hasNums[i]){
         res = Math.max(res,mins[i]-firstMax);
         firstMax = maxs[i]
     }
 }
 return res
}
function getBucketIndex(value,bucketLength,min,max){
  return Math.floor((value-min)*bucketLength/(max-min))
}
文章目录
  1. 1. 小范围排序练习题
  2. 2. 重复值判断练习题
  3. 3. 荷兰国旗问题
  4. 4. 有序矩阵查找练习题
  5. 5. 最短子数组
  6. 6. 相邻两数最大差值练习题