• 排序问题思考(要求时间和空间复杂度尽可能的低)【Part 1】


    题目:

    有一个无序整型数数组,如何求出这个数组排序后的任意两个相邻元素的最大差值?要求时间和空间复杂度尽可能低。(例如:无序数组 2、3、1、4、6,排序后是1、2、3、4、6,最大差值是 6-4=2)

    解题思路分析:

    用一种较快的稳定排序算法(比如归并算法,时间复杂度N*logN)给原数组排序,然后遍历排好序的数组,每两个相邻元素求差,最终得到最大差值。 

    该解法的时间复杂度是O(N*logN),在不改变原数组的情况下,空间复杂度是O(N)。

    但是,这个题的本意,其实不是纯粹的排序问题

    要处理这个问题,可以从要求上出发考虑,即什么排序算法的时间复杂度比O(N*logN)还要低? 嗯,从这点出发,似乎可以找到答案,回顾排序算法,比归并算法还要快的,是计数排序以及桶排序算法了。

    那下面,就先从计数排序开始分析:

    1.利用计数排序的思想,先求出原数组的最大值Max与最小值Min的区间长度k(k=Max-Min+1)。 

    2.创建一个长度为k的新数组Array。 

    3.遍历原数组,把原数组每一个元素插入到新数组Array对应的位置,比如元素的值为n,则插入到Array[n-min]当中。此时Array的部分位置为空,部分位置填充了数值。 

    4.遍历新数组Array,统计出Array中最大连续出现空值的次数+1,即为相邻元素最大差值。

    例如给定无序数组 { 2、6、3、4、5、10、9 },处理过程如下图:

    该解法的时间复杂度为O(n+k),空间复杂度同样是O(n+k)。

    下面看看其java代码实现过程:

      1 /**
      2  * @author "shihuc"
      3  * @date   2017年1月11日
      4  */
      5 package jishuSort;
      6 
      7 import java.io.File;
      8 import java.io.FileNotFoundException;
      9 import java.util.Arrays;
     10 import java.util.Scanner;
     11 
     12 /**
     13  * @author chengsh05
     14  *
     15  */
     16 
     17 class MaxMin {
     18     int max;
     19     int min;
     20     /**
     21      * @return the max
     22      */
     23     public int getMax() {
     24         return max;
     25     }
     26     /**
     27      * @param max the max to set
     28      */
     29     public void setMax(int max) {
     30         this.max = max;
     31     }
     32     /**
     33      * @return the min
     34      */
     35     public int getMin() {
     36         return min;
     37     }
     38     /**
     39      * @param min the min to set
     40      */
     41     public void setMin(int min) {
     42         this.min = min;
     43     }
     44 }
     45 
     46 public class Algorithm {
     47 
     48     /**
     49      * @param args 
     50      */
     51     public static void main(String[] args) {
     52         
     53         File file = new File("./src/jishuSort/sample.txt");
     54         Scanner sc = null;
     55         try {
     56             sc = new Scanner(file);
     57             int N = sc.nextInt();
     58             for(int i=0; i<N; i++){
     59                 int S = sc.nextInt();
     60                 int data[] = new int[S];
     61                 for(int j=0; j<S; j++){
     62                     data[j] = sc.nextInt();
     63                 }
     64                 MaxMin mm = getMaxMin(data);
     65                 int mArr[] = getMinusArray(data, mm);
     66                 int minus = getTarget(mArr, mm.getMin() - 1);
     67                 System.out.println(i + " -- >  " + minus);                
     68             }            
     69         } catch (FileNotFoundException e) {
     70             // TODO Auto-generated catch block
     71             e.printStackTrace();
     72         } finally {
     73             if(sc != null){
     74                 sc.close();
     75             }
     76         }        
     77     }
     78     
     79     /**
     80      * 在时间复杂度为O(n)情况下,计算出最大值与最小值
     81      * 
     82      * @param da
     83      * @return
     84      */
     85     public static MaxMin getMaxMin(int da[]){
     86         MaxMin mm = new MaxMin();
     87         int max = Integer.MIN_VALUE;
     88         int min = Integer.MAX_VALUE;
     89         for(int i=0; i<da.length; i++){
     90             if(da[i] > max){
     91                 max = da[i];
     92             }
     93             if(da[i] < min){
     94                 min = da[i];
     95             }
     96         }
     97         
     98         mm.setMax(max);
     99         mm.setMin(min);
    100         return mm;
    101     }
    102     
    103     /**
    104      * 获取最大值与最小值之间的距离 k
    105      * 
    106      * @param mm
    107      * @return k
    108      */
    109     public static int getDistance(MaxMin mm){
    110         return mm.getMax() - mm.getMin() + 1;
    111     }
    112     
    113     /**
    114      * 获取差值数组,即原数组中的每个数与最小值的差值位置处放置原数组的元素
    115      * 
    116      * @param da 原数组
    117      * @param mm 最大最小值对象
    118      * @return 差值数组
    119      */
    120     public static int[] getMinusArray(int da[], MaxMin mm){
    121         int K = getDistance(mm);
    122         int min = mm.getMin();
    123         
    124         int minusArray[] = new int[K];
    125         //将数组初始化为全mm.getMin() - 1的值, 假设,这里的mm.getMin()比Integer.MIN_VALUE大,自己分析
    126         Arrays.fill(minusArray, mm.getMin() - 1); 
    127         
    128         for(int i=0; i<da.length; i++){
    129             int n = da[i];
    130             minusArray[n - min] = n; 
    131         }
    132         
    133         return minusArray;
    134     }
    135     
    136     /**
    137      * 找出连续出现空值的最大个数,注意,是两个数之间的差距,所以,最后要补加一个1    
    138      * 
    139      * @param minusArr
    140      * @param empty
    141      * @return
    142      */
    143     public static int getTarget(int minusArr[], int empty){
    144         int size = 0;
    145         int temp = 0;
    146         for(int i=0; i<minusArr.length; i++){
    147             if(minusArr[i] == empty){
    148                 temp++;
    149             }else{
    150                 if(temp > size){
    151                     size = temp;                    
    152                 }
    153                 temp = 0;
    154             }
    155         }
    156         return size + 1;
    157     }
    158 }

    附加程序中用到的测试数据sample.txt:

    1 2
    2 7
    3 2 6 3 4 5 10 9
    4 5
    5 2 3 1 4 6

    数据中第一行,表示有多少个测试案例,后续每两行表示一个测试里,上一行是测试数组元素个数,下一行表示数组元素的内容。

    测试运行后的结果如下:

    1 0 -- >  3
    2 1 -- >  2

    今天,就只说到这里吧,仅仅将计数排序实现了下,里面有个注意的地方,就是如何判断差值数组的内容是空,请读者自行分析。

    后续将补充桶排序的实现方案!

  • 相关阅读:
    Aseprite+Cocos:打包像素画图,导入到cocos里并动起来
    自定义博客园个人皮肤
    埃航和737MAX坠毁:软件优先级问题
    淘宝网——软件质量属性场景分析
    王概凯《架构漫谈》阅读笔记
    2965 -- The Pilots Brothers' refrigerator
    UVa10082 -- WERTYU
    1753 -- Flip Game
    1083 -- Moving Tables
    2159 -- Ancient Cipher
  • 原文地址:https://www.cnblogs.com/shihuc/p/6272828.html
一二三 - 开发者的网上家园