Java数据结构和算法(2)--《Java数据结构和算法》第二版 Robert lafore第二章【数组】编码作业

用户2032165

发布于 2018-06-05 16:49:05

8150

发布于 2018-06-05 16:49:05

文章被收录于专栏：cmazxiaoma的架构师之路cmazxiaoma的架构师之路

前言

最近在在看《Java数据结构和算法》这本书，这本书很不错，值得细看。看完了第二章-数组篇。所以写这一篇章节小结，正好附上自己写的编程作业源码，供大家参考。

书里小结

Java中的数组是对象，由new运算符操作。
无序数组可以提供快速的插入，但查找和删除很慢。
将数组封装到类中可以保护数组不被随意的更改。
类中的接口由类用户可访问的方法(有时还有字段)组成。
有序数组可以使用二分查找。
线性查找需要的时间和数组中的数据项的个数成正比。
二分查找需要的时间与数组中数据项的个数的对数成正比。
大O表示法为比较算法的速度提供一个方便的方法。大O表示是一个可以描述算法的速度是如何与数据项的个数相联系的比较。

梳理知识点

在有序数组中，如果用二分法插入的话，插入20W条数据，自己测试的时间是43毫秒。如果用线性插入的话，所需的时间是很大的。线性插入的时间复杂度是O(n),二分法插入的时间复杂度是O(logN)。
在有序数组中，用线性查找和二分法查找，二分法查找效率要比线性查找效率高。线性查找的时间复杂度是O(n),二分法查找的时间复杂度是O(logN)。
O(1)意味着一个操作执行了常数的时间
简单类型变量和对象都可以存入数组。

课后编码作业

课后编码作业还是有一点难的，也花了很长时间去写，在此附上源码。

2.1 向highArray.java程序（清单2.3）的HighArray类添加一个名为getMax()的方法，它返回数组中最大关键字的值，当数组为空时返回-1。向main()中添加一些代码来使用这个方法。可以假设所有关键字都是正数。
2.2 修改编程作业2.1中的方法，使之不仅返回最大的关键字，而且还将该关键字从数组中删除。将这个方法命名为removeMax()。
2.3 编程作业2.2中的removeMax()方法提供了一种通过关键字值进行数组排序的方法。实现一个排序方案，要求不修改HighArray类，只需对main()中的代码进行修改。这个方法需要第二个数组，在排序结束时数组数据项是逆序排列的。（这个方法是第3章“简单排序”中选择排序的一个变体。)

public class HighArray {
    
    private long[] a;
    public int size;
    private HighArrayReverseSort highArrayReverseSort;
    
    public HighArray(HighArrayReverseSort highArrayReverseSort,int initialCapacity){
        this.highArrayReverseSort=highArrayReverseSort;
        a=new long[initialCapacity];
        size=0;
    }
    
    
    public boolean find(long findValue){
        int j;
        for(j=0;j<size;j++){
            
            if(a[j]==findValue){
                break;
            }
        }
        
        if(j==size){
            return false;
        }else{
            return true;
        }
        
    }
    
    public void insert(long value){
        a[size]=value;
        size++;
    }
    
    public boolean delete(long value){
        int j;
        for(j=0;j<size;j++){
            
            if(a[j]==value){
                break;
            }
        }
        
        if(j==size){
            return false;
        }else{
            
            for(int k=j;k<size-1;k++){
                a[k]=a[k+1];
            }
            size--;
            return true;
        }
    }
    
    public void display(){
        for(int j=0;j<size;j++){
            System.out.print(" "+a[j]);
        }
        System.out.print("\n");
    }
    
    public long getMax(){
        if(size==0){
            return -1;
        }else{
            long max=a[0];
            for(int j=0;j<size;j++){
                
                if(a[j]>max){
                    max=a[j];
                }
            }
            return max;
        }
    }
    
    public boolean removeMax(){
        highArrayReverseSort.reverseSort(this);
        return delete(getMax());
    }
    
    public int size(){
        return size;
    }
    
    public long get(int index){
        return a[index];
    }
    
    public long set(int index,long value){
        long oldValue=this.get(index);
        a[index]=value;
        return oldValue;
    }
}

public interface HighArrayReverseSort {
    
    public void reverseSort(HighArray array);

}

public class HighArrayTest{
    

    public static void main(String[] args){
        
        HighArray array=new HighArray(new HighArrayReverseSort() {
            
            @Override
            public void reverseSort(HighArray a) {
                class Inner{
                    
                    public void swap(int m,int i){
                        long temp=a.get(m);
                        a.set(m, a.get(i));
                        a.set(i, temp);
                    }
                }
                // TODO Auto-generated method stub
                for(int i=0;i<a.size();i++){
                    //最大值的小标
                    int m=i;
                    for(int k=i+1;k<a.size();k++){
                        
                        if(a.get(k)>a.get(m)){
                            m=k;
                        }
                    }
                    
                    //如果待排序中的最大元素的下标等于i的话，那么就不用排序
                    //i是每次循环默认的最大元素的下标
                    if(m!=i){
                        new Inner().swap(m,i);
                    }
                }
                
                a.display();
                
            }
        },100);
        
        array.insert(23);
        array.insert(343);
        array.insert(2543);
        array.insert(234);
        array.insert(23);
        array.insert(233);
        array.insert(230);
        array.insert(253);
        array.insert(223);
        array.insert(2);
        
        array.display();
        
        
        System.out.println("最大数="+array.getMax());
        
        array.removeMax();
        
        array.display();
    }
}

2.4 修改orderedArray.java程序（清单2.4）使insert()、delete()与find()方法一样都使用二分查找，正如书中所建议的那样。

public class OrderedArray {
    
    
    private long[] a;
    private int size;
    
    public OrderedArray(int inititalCapacity){
        
        a=new long[inititalCapacity];
        size=0;
    }
    
    public int linearFind(long searchValue){
        long startTime=System.currentTimeMillis();
        int j;
        
        for(j=0;j<size;j++){
            
            if(searchValue==a[j]){
                
                break;
            }
        }
        
        if(j==size){
            long noFoundTime=System.currentTimeMillis();
            System.out.println("本次是线性查询,查询的数字="+searchValue+",耗时="+(noFoundTime-startTime));
            return size;
        }else{
            long endTime=System.currentTimeMillis();
            System.out.println("本次是线性查询，查询的数字="+searchValue+",返回索引="+j+",查询时间="+(endTime-startTime));
            return j;
        }
    }
    
    public int fastFind(long searchValue){
        System.out.println("进行了二分法查询");
        long startTime=System.currentTimeMillis();
        int start=0;
        int end=size-1;
        int mid;
        while(start<=end){
            
        mid=(start+end)>>1;
        System.out.println("start="+start+",end="+end+",mid="+mid);
        
        long value=a[mid];
        if(searchValue>value){
            start=mid+1;
        }else if(searchValue<value){
            end=mid-1;
        }else{
            long endTime=System.currentTimeMillis();
            System.out.println("本次是二分法查询，查询的数字="+searchValue+",返回索引="+mid+",查询时间="+(endTime-startTime));
            return mid;
        }
        }
        long noFoundTime=System.currentTimeMillis();
        System.out.println("本次是二分法查询，没找到该数字="+searchValue+",耗时="+(noFoundTime-startTime));
        return -1;
    }
    
    
    public void fastInsert(long insertValue){
        int start=0;
        int end=size-1;
        int mid;
        
        while(start<=end){
            
            mid=(start+end)/2;
            
            long value=a[mid];
            
            if(insertValue>value){
                
                start=mid+1;
                
            }else{
                end=mid-1;
            }
            
        }
        
        
        for(int k=size;k>start;k--){
            
            a[k]=a[k-1];
        }
        
        a[start]=insertValue;
        size++;
    }
    
    /**
     * 线性插入
     * @param value
     */
    public void linearInsert(long value){
        
        int j;
        
        for(j=0;j<size;j++){
            
            if(a[j]>value){
                
                break;
            }
        }
        
        for(int k=size;k>j;k--){
            
            a[k]=a[k-1];
        }
        a[j]=value;
        System.out.println("线性插入，此时数组size="+size);
        size++;
    }
    public boolean delete(long value){
        
        int i=fastFind(value);
        
        if(i==size){
            return false;
        }else{
            
            for(int k=i;k<size-1;k++){
                
                a[k]=a[k+1];
            }   
            size--;
            return true;
        }
    }
    
    
    public void display(){
        for(int j=0;j<size;j++){
            System.out.println(""+a[j]);
        }
    }
    
    public int size(){
        return size;
    }
    
    public void removeAll(){
        size=0;
    }
    
    public long get(int index){
        return a[index];
    }
}

public class OrderedArrayTest {
    
    public static void main(String[] args){
        
        long t1,t2,t3,t4,t5,t6;
        int initialCapacity=400000;
        OrderedArray array=new OrderedArray(initialCapacity);
        //二分法插入
        t1=System.currentTimeMillis();
        for(int i=0;i<200000;i++){
            array.fastInsert(i);
        }
        t2=System.currentTimeMillis();
        t3=t2-t1;
        System.out.println("二分法插入"+array.size()+"条数据，耗时="+t3+"毫秒");
        /**删除123456**
         *
         */
        boolean flag=array.delete(123456);
        String msg=flag?"删除成功":"删除失败";
        System.out.println("msg="+msg);
        /***************线性插入******************/
        t4=System.currentTimeMillis();
        for(int i=200000;i<400000;i++){
            array.linearInsert(i);
        }
        t5=System.currentTimeMillis();
        t6=t5-t4;
        System.out.println("线性插入"+200000+"条数据，耗时="+t6+"毫秒");
        
        long searchValue=321234;
        /**二分法查询**/
        int index=array.fastFind(searchValue);
        /**线性查询**/
        array.linearFind(searchValue);
    }
    
    
}

【2.5】向orderedArray.java程序（清单2.4）的OrdArray类加入一个merge()方法，使之可以将两个有序的源数组合并成一个有序的目的数组。在main()中添加代码，向两个源数组中插入随机数，调用merge()方法，并将结果目的数组显示出来。两个源数组的数据项个数可能不同。在算法中需要先比较源数组中的关键字，从中选出最小的一个数据项复制到目的数组。同时还要考虑如何解决当一个源数组的数据项已经取完而另一个还剩一些数据项情况。

public class NewOrderedArray extends OrderedArray{

    
    public NewOrderedArray(int inititalCapacity) {
        super(inititalCapacity);
        // TODO Auto-generated constructor stub
    }

    
    public void merge(NewOrderedArray oldArray1){
        NewOrderedArray oldArray2=this;
        NewOrderedArray newArray=new NewOrderedArray(oldArray1.size()+oldArray2.size());
        for(int i=0;i<oldArray1.size();i++){
            newArray.fastInsert(oldArray1.get(i));
        }
        for(int j=0;j<oldArray2.size();j++){
            newArray.fastInsert(oldArray2.get(j));
        }
        
        newArray.display();
    }


    @Override
    public void display() {
        // TODO Auto-generated method stub
        for(int j=0;j<this.size();j++){
            System.out.print(" "+this.get(j));
        }
        System.out.print("\n");
    }
    
    
}

public class NewOrderedArrayTest {
    
    public static void main(String[] args){
        
        NewOrderedArray oldArray1=new NewOrderedArray(10);
        NewOrderedArray oldArray2=new NewOrderedArray(10);
        
        for(int i=0;i<10;i++){
            oldArray1.fastInsert(new Random().nextInt(9999));
            oldArray2.fastInsert(new Random().nextInt(666));
        }
        
        oldArray1.display();
        oldArray2.display();
        oldArray1.merge(oldArray2);
    }
    
}

【2.6】向highArray.java程序（清单2.3）的HighArray类中加入一个noDup()方法，使之可以将数组中的所有重复数据项删除。即如果数组中有三个数据项的关键字为17，noDup()方法会删除其中的两个。不必考虑保持数据项的顺序。一种方法是先用每一个数据项同其他数据项比较，并用null (或是一个不会用在真正的关键字中的特殊值)将重复的数据项覆盖掉。然后将所有的null删除，当然还要缩小数组的大小。

public class NewHighArray extends HighArray{

    public NewHighArray(HighArrayReverseSort highArrayReverseSort, int initialCapacity) {
        super(highArrayReverseSort, initialCapacity);
        // TODO Auto-generated constructor stub
    }
    
    public void noDup(long value){
        
        //第一种方法
        int NULL=-1;
        
        for(int i=0;i<size;i++){
            
            if(this.get(i)==value){
                this.set(i,NULL);
            }
        }
        
        for(int j=0;j<this.size();j++){
            
            if(this.get(j)==NULL){
                
                System.out.println("j="+j);
                for(int k=j;k<size-1;k++){
                    
                    this.set(k, get(k+1));
                }
                size--;
                j--;
                //因为删除了一个元素,j下标对应的元素会发生改变,所以j-1后才能正确访问填充j下标的元素
                System.out.println("size="+size);
            }
        }
        this.insert(value);
    }
}

public class NewHighArrayTest {

    
    public static void main(String[] args){
        
        int initialCapacity=10;
        NewHighArray array=new NewHighArray(new HighArrayReverseSort() {
            
            @Override
            public void reverseSort(HighArray array) {
                // TODO Auto-generated method stub
                
            }
        },initialCapacity);
        
        array.insert(56);
        array.insert(23);
        array.insert(15);
        array.insert(66);
        array.insert(67);
        array.insert(15);
        array.insert(100);
        array.insert(90);
        array.insert(15);
        array.insert(15);
        
        array.display();
        
        long  dupValue=15;
        array.noDup(dupValue);
        
        array.display();
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017.07.06 ，如有侵权请联系 cloudcommunity@tencent.com 删除

java