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

前言

最近在在看《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();
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android机器圈

递归 —— 二分查找法 —— 归并排序

二分法就是把一个数组折半查找,再折半直到找到数据位置,或者无数据位置。比如说1-100,你选的值是23,那么范围写法就是(索引写法类似)

1754
来自专栏恰同学骚年

数据结构基础温故-2.栈

现实生活中的事情往往都能总结归纳成一定的数据结构,例如餐馆中餐盘的堆叠和使用,羽毛球筒里装的羽毛球等都是典型的栈结构。而在.NET中,值类型在线程栈上进行分配,...

803
来自专栏个人随笔

Java 关于集合框架那点事儿

 1.引入集合框架   采用数组存在的一些缺陷:    1.数组长度固定不变,不能很好地适应元素数量动态变化的情况。    2.可通过数组名.length获取数...

29110
来自专栏技术博客

C#基础知识系列十(集合)

  本节主要是来了解学习集合,以方便在程序编写时,什么地方该选用什么集合,让程序更健壮的运行起来。在学习了解集合之前,首先需要了解一些数据结构方面的知识。下面我...

1203
来自专栏desperate633

LintCode 二分查找题目分析代码

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组...

912
来自专栏java初学

13.2 具体的集合

2749
来自专栏机器学习入门

挑战程序竞赛系列(89):3.6平面扫描(3)

挑战程序竞赛系列(89):3.6平面扫描(3) 传送门:POJ 3292: Rectilinear polygon 题意参考hankcs: http://w...

2025
来自专栏JackeyGao的博客

Leetcode 算法 -4. Median of Two Sorted Arrays

解题思路: 先把列表碾平 , 由于两个列表元素类型相同直接相加即可. 然后排序. 计算中间位置, 可以通过判断奇偶数来分别处理开始index和结束index....

753
来自专栏顶级程序员

判断链表是否有环

判断一个单向链表是否有环。(指向表头结点的指针为head) 方法一: (1)用两个指针p1和p2分别指向表头结点,即p1=p2=head (2)p1和p2分别...

4597
来自专栏mathor

ST算法

 RMQ(Range Minimum/Maximum Query),即区间最值查询。对于长度为n的数列arr,回答若干询问Q(i,j),返回数列arr中下标在i...

1972

扫码关注云+社区

领取腾讯云代金券