转载

不要小瞧数组

一、使用java中的数组

数组：把数据码成一排进行存放

public class array {

    public static void main(String[] args ){

        //定义数组指定长度
        int[] arr = new int[10];
        for (int i = 0; i<arr.length; i++)
            arr[i] = i;

        //
        int[] scores = new int[]{100,99,66};
        for (int i = 0; i<scores.length; i++)
            System.out.println(scores[i]);

        // 数组可遍历
        scores[0] = 98;
        for (int score: scores)
            System.out.println(score);

    }
}

二、二次封装属于我们自己的数组

数组最大的优点：快速查询 score[2]

数组最好应用于“索引有语意”的情况

但并非所有有语意的索引都适合用于数组，例如身份证号

数组也可以处理“索引没有语意”的情况，这里主要处理“索引没有语义”的情况数组的使用

public class array {

    private int[] data;
    private int size;

    // 构造函数,传入数组的容量capacity构造array
    public array(int capacity){
        data = new int[capacity];
        size = 0;
    }

    // 无参数的构造函数，默认数组容量capaciay=10
    public array(){
        this(10);
    }

    // 获取数组中的元素个数
    public int getSize(){
        return size;
    }

    // 获取数组的容量
    public int getCapacity(){
        return data.length;
    }

    // 判断数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }

}

三、向数组添加元素

向数组末尾添加元素，还是在上面的类中添加方法

// 向所有元素后添加一个新元素
    public void addList(int e){

        // 如果元素的个数等于数组的容量，那么抛出异常
        if (size == data.length)
            throw new IllegalArgumentException("AddLast failed. array is full");
        data[size] =  e;
        size++;
    }

指定位置添加元素

// 在第index个位置插入一个新元素e
    public void add(int index,int e){

        if (size == data.length)
            throw new IllegalArgumentException("Add failed. array is full");

        if (index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. array is full");
        }

        for (int i = size - 1; i >= index; i--){
            data[i+1] = data[i];
        }

        data[index] = e;
        size++;

    }

在元素前面添加一个新元素

// 在所有元素前添加一个新元素
    public void addFirst(int e){
        add(0,e);
    }

四、数组中查询元素和修改元素

还是在上面的类中写方法，这里重写toString方法，用于查询元素

@Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("array: size = %d , capacity = %d/n",size,data.length));

        res.append('[');
        for (int i = 0 ; i < size; i++){
            res.append(data[i]);
            if(i != size - 1)
                res.append(",");
        }
        res.append(']');
        return  res.toString();
    }

获取元素以及修改元素

// 获取index索引位置的元素
    int get(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("GET failed. array is full");
        return data[index];
    }


    // 修改index索引位置的元素e
    void set (int index,int e){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("set failed. array is full");
        data[index] = e;
    }

把前面写的功能进行测试

public class Main {

    public static void main(String[] args ){

        array arr = new array(20);
        for (int i = 0 ; i < 10 ; i++){
            arr.addList(i);
        }

        System.out.println(arr);

        // 索引为1的位置添加100
        arr.add(1,100);
        System.out.println(arr);

        // 开始添加-1
        arr.addFirst(-1);
        System.out.println(arr);

    }
}

// 打印结果
array: size = 10 , capacity = 20
[0,1,2,3,4,5,6,7,8,9]
array: size = 11 , capacity = 20
[0,100,1,2,3,4,5,6,7,8,9]
array: size = 12 , capacity = 20
[-1,0,100,1,2,3,4,5,6,7,8,9]

五、包含，搜索和删除

还是在上面的类中写方法，包含

// 查找数组中是否有元素e
public boolean contains(int e){
        for (int i = 0 ; i < size ; i++){
            if (data[i] == e){
                return true;
            }
        }
        return false;
    }

搜索

// 查找数组中元素e所在的索引，如果元素不存在，返回-1
    public int find(int e){
        for (int i = 0 ; i < size ; i++){
            if (data[i] == e){
                return i;
            }
        }
        return -1;
    }

删除

// 从数组中删除index位置的元素，返回删除的元素
    public int remove(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed");

        int ret = data[index];
        for (int i = index + 1 ; i < size ; i++)
            data [ i - 1] = data[i];
        
        // 这个地方需要注意
        size --;
        return ret;
    }


    // 从数组中删除第一个元素，返回删除的元素
    public int removeFirst(){
        return remove(0);
    }
    // 从数组中删除最后一个元素，返回删除的元素
    public int removeLast(){
        return remove(size - 1);
    }


    // 从数组中删除元素e
    public void removeElement(int e){
        int index = find(e);
        if (index != -1){
            remove(index);
        }
    }

进行测试

public class Main {

    public static void main(String[] args ){

        array arr = new array(20);
        for (int i = 0 ; i < 10 ; i++){
            arr.addList(i);
        }

        System.out.println(arr);

        arr.add(1,100);
        System.out.println(arr);

        arr.addFirst(-1);
        System.out.println(arr);


        arr.remove(2);
        System.out.println(arr);

        arr.removeElement(4);
        System.out.println(arr);

        arr.removeFirst();
        arr.removeLast();
        System.out.println(arr);
    }
}

array: size = 10 , capacity = 20
[0,1,2,3,4,5,6,7,8,9]
array: size = 11 , capacity = 20
[0,100,1,2,3,4,5,6,7,8,9]
array: size = 12 , capacity = 20
[-1,0,100,1,2,3,4,5,6,7,8,9]
array: size = 11 , capacity = 20
[-1,0,1,2,3,4,5,6,7,8,9]
array: size = 10 , capacity = 20
[-1,0,1,2,3,5,6,7,8,9]
array: size = 8 , capacity = 20
[0,1,2,3,5,6,7,8]

基本功能已经实现，但是还是有很多需要完善的地方。

六、使用泛型

  1. 让我们的数据结构可以放置任何的数据类型
  2. 不可以是基本数据类型，只能是类对象：boolean、byte、chat、short、int、long、float、double
  3. 每个基本数据类型都有对应的包装类：Boolean、Byte、Chat、Short、Int、Long、Float、Double
  4. 下面还是针对上面的进行修改，由于使用了泛型，这里将array类全部放在这里方便大家观看
public class array<E> {

    // 数据类型由之前的int改成现在的
    private E[] data;
    private int size;


    // 构造函数,传入数组的容量capacity构造array
    // 这里使用了强制类型转化
    public array(int capacity){
        data = (E[]) new Object[capacity];
        size = 0;
    }

    // 无参数的构造函数，默认数组容量capaciay=10
    public array(){
        this(10);
    }


    // 获取数组中的元素个数
    public int getSize(){
        return size;
    }

    // 获取数组的容量
    public int getCapacity(){
        return data.length;
    }

    // 判断数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 向所有元素后添加一个新元素，转入参数类型改变
    public void addLast(E e){

        // 如果元素的个数等于数组的容量，那么抛出异常
        if (size == data.length)
            throw new IllegalArgumentException("AddLast failed. array is full");
        data[size] =  e;
        size++;

    }


    // 在所有元素前添加一个新元素，转入参数类型改变
    public void addFirst(E e){
        add(0,e);
    }

    // 在第index个位置插入一个新元素e，转入参数类型改变
    public void add(int index,E e){

        if (size == data.length)
            throw new IllegalArgumentException("Add failed. array is full");

        if (index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. array is full");
        }

        for (int i = size - 1; i >= index; i--){
            data[i+1] = data[i];
        }

        data[index] = e;
        size++;


    }



    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("array: size = %d , capacity = %d/n",size,data.length));

        res.append('[');
        for (int i = 0 ; i < size; i++){
            res.append(data[i]);
            if(i != size - 1)
                res.append(",");
        }
        res.append(']');
        return  res.toString();

    }


    // 获取index索引位置的元素，返回类型改变
    E get(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("GET failed. array is full");
        return data[index];
    }


    // 修改index索引位置的元素e，转入参数类型改变
    void set (int index,E e){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("set failed. array is full");
        data[index] = e;
    }


    // 查找数组中是否有元素e
    public boolean contains(E e){
        for (int i = 0 ; i < size ; i++){
            if (data[i] .equals(e) ){
                return true;
            }
        }
        return false;
    }


    // 查找数组中元素e所在的索引，如果元素不存在，返回-1，转入参数类型改变
    public int find(E e){
        for (int i = 0 ; i < size ; i++){
            if (data[i] .equals(e) ){
                return i;
            }
        }
        return -1;
    }

    // 从数组中删除index位置的元素，返回删除的元素，返回类型改变
    public E remove(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed");

        E ret = data[index];
        for (int i = index + 1 ; i < size ; i++)
            data [ i - 1] = data[i];
        size --;
        // data[size] = null;    // loitering objects
        return ret;
    }


    // 从数组中删除第一个元素，返回删除的元素
    public E removeFirst(){
        return remove(0);
    }
    // 从数组中删除最后一个元素，返回删除的元素
    public E removeLast(){
        return remove(size - 1);
    }

    // 从数组中删除元素e
    public void removeElement(E e){
        int index = find(e);
        if (index != -1){
            remove(index);
        }
    }

}

为了进行测试，从新建一个Student类来进行测试，这样就可以使用任意类型的数据

public class Student {

    private String name;
    private int score;

    public Student(String studentName, int studentScore){
        name = studentName;
        score = studentScore;
    }

    @Override
    public String toString() {
        return String.format("Student(name: %s , score: %d)/n",name,score);
    }

    public static void main(String[] args){

        // 使用泛型
        array<Student> arr = new array<>();
        arr.addLast(new Student("Alice",100));
        arr.addLast(new Student("Bob",88));
        arr.addLast(new Student("Char",66));

        System.out.println(arr);
    }

}
public class Student {

    private String name;
    private int score;

    public Student(String studentName, int studentScore){
        name = studentName;
        score = studentScore;
    }

    @Override
    public String toString() {
        return String.format("Student(name: %s , score: %d)/n",name,score);
    }

    public static void main(String[] args){

        // 使用泛型
        array<Student> arr = new array<>();
        arr.addLast(new Student("Alice",100));
        arr.addLast(new Student("Bob",88));
        arr.addLast(new Student("Char",66));

        System.out.println(arr);
    }


}

array: size = 3 , capacity = 10
[Student(name: Alice , score: 100)
,Student(name: Bob , score: 88)
,Student(name: Char , score: 66)
]

说明还是成功的，由于int类型太单调，之后都将使用泛型来进行操作

七、动态数组

由于数组是由限制的，在用户不知道数据的个数的时候，容易抛出异常，这个时候就要使用动态数组，而不用再考虑数据的个数

具体的实现，还是在array类中

// 动态数组
    private void resize(int newCapacity){
        // 使用泛型，强制类型转换
        E[] newData = (E[])new Object[newCapacity];

        // 把之前数组中的数据传到新的数组中
        for (int i = 0 ; i < size ; i ++){
            newData[i] = data[i];
        }
        //新的数组再指向到原来的数组，狸猫换太子
        data = newData;

    }

把添加元素的方法进行改写，

public void add(int index,E e){

        // 如果数组已经满了
        if (size == data.length)
//            throw new IllegalArgumentException("Add failed. array is full");
            // 调用动态数组，扩容到之前容量的二倍
            resize(2 * data.length);


        if (index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. array is full");
        }

        for (int i = size - 1; i >= index; i--){
            data[i+1] = data[i];
        }

        data[index] = e;
        size++;


    }

把删除元素的方法也进行改写

public E remove(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed");

        E ret = data[index];
        for (int i = index + 1 ; i < size ; i++)
            data [ i - 1] = data[i];
        size --;
        // data[size] = null;    // loitering objects

        // 如果数组中剩余的数量是数组长度的二倍，那么就把数组的长度减半
        if (size == data.length / 2)
            resize(data.length / 2);

        return ret;
    }

进行测试

public class Main {

    public static void main(String[] args ){

        // int类型的包装类
        array<Integer> arr = new array<>(5);

        for (int i = 0 ; i < 5 ; i++){
            arr.addLast(i);
        }

        System.out.println(arr);

        arr.add(1,100);
        System.out.println(arr);

        arr.addFirst(-1);
        System.out.println(arr);


        arr.remove(2);
        System.out.println(arr);

        arr.removeElement(4);
        System.out.println(arr);

        arr.removeFirst();
        arr.removeLast();
        System.out.println(arr);
    }
}

array: size = 5 , capacity = 5
[0,1,2,3,4]
当数据多的时候，自动扩容的之前的两倍
array: size = 6 , capacity = 10
[0,100,1,2,3,4]
array: size = 7 , capacity = 10
[-1,0,100,1,2,3,4]
array: size = 6 , capacity = 10
[-1,0,1,2,3,4]
当数据少的时候，自动缩少两倍
array: size = 5 , capacity = 5
[-1,0,1,2,3]
array: size = 3 , capacity = 5
[0,1,2]

这样就基本实现了动态的数组

八、简单的时间复杂度分析

  1. O(1)，O(n)，O(lgn)，O(nlogn)，O(n^2)
  2. 大O描述的是算法的运行时间和输入数据之间的关系
public static int sum(int[] nums){
    int sun = 0;
    for(int num: nums) sum += num;
    return sum;
}

这里算法是O(n)，这里n是nums中元素的个数

也就是说这个算法运行的时间的多少和这里的nums中元素的个数呈线性关系，也就是nums中的个数越多时间就越多

  1. 为什么要用大O，叫做O(n)？忽略常数，实际时间(线性)

    $$

    T = c1*n + c2

    $$

具体分析算法的时候就直接忽略常数， 渐进时间复杂度，描述n趋近于无穷的情况

T = 2*n + 2 O(n)
T = 2000*n + 1000 O(n)
T = n n 1 + 0 O(n^2)
T = 2 n n + 300*n + 10 O(n^2)

其中n的幂数越大性能越差

分析动态数组的时间复杂度

向数组头添加元素的时候，要把数组中的每一个元素往后面移动，所以是O(n)，整体来看， 通常做最坏的打算 ，也是O(n)，添加的还有注意resize方法

添加操作 O(n)
addLast(e) O(1)
addFirst(e) O(n)
add(index,e) O(n/2) = O(n)
resize O(n)

删除操作和上面的一样，也是做最坏的打算，也是O(n)，删除时还要注意resize方法

删除操作 O(n)
removeLast(e) O(1)
removeFirst(e) O(n)
remove(index,e) O(n/2) = O(n)

修改操作，这个是最简单的，O(1)

修改操作 O(1)
set(index,e) O(1)

查找操作，也是O(n)

查找操作 O(n)
get(index) O(1)
contains(e) O(n)
find(e) O(n)

总结

增 O(n)
删 O(n)
改 已知索引O(1)，未知索引O(n)
查 已知索引O(1)，未知索引O(n)

注意：对于增和删，如果只对最后一个元素操作依然是O(n)？，因为resize方法？

九、均摊复杂度和防止复杂度的震荡

  1. resize的复杂度分析

从最坏的方面来看， addLast(e)的复杂度是O(1) ，如果此时数组容量不够需要扩容的时候就要调用resize方法， 但是resize方法的复杂度是O(n) ，所以综合来说 addLast(e)的复杂度是O(n) ，但是也不是每一次添加就会扩容，所以用最坏的来分析有点不合理，这里用到下面的知识了

假设当前的capacity = 8 ，并且每一次添加操作都使用addLast

$$

1+1+1+1+1+1+1+1+8+1

$$

9次addLast操作，触发resize，总共进行了17次的基本操作，9次添加，8次转移，

平均来说也就是每次addLast操作，进行了大约两次基本操作

假设capacity = n，n+1次addLast，触发resize，总共进行2n+1次基本操作

平均，每次addLast操作，进行2次基本操作

这样均摊计算，时间复杂程度是O(1)

所以在这个例子中，均摊计算，比计算最坏情况有意义

  1. 均摊复杂度

addLast的均摊复杂度是O(1)

同理，removeLast的均摊复杂度也是O(1)

  1. 复杂度的震荡

但是，我们同时来看addLast和removeLast操作

当capacity = n时，调用addLast，这里进行扩容，复杂度O(n)，然后执行removeLast，进行缩容，复杂度也是O(n)，如此循环，复杂度就一直是O(n)了

出现问题的原因：removeLast是resize过于着急(Eager)，不必一下子就缩容

解决方案：Lazy，当数据是总长度的1/4时进行缩容，缩容还是变回原来的一半

当size == capacity /4 时，才将capacity减半

通过这样的方法，就解决了复杂度震荡的问题

下面用代码实现，还是在array类中修改，把remove方法改写就可以了，

public E remove(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed");

        E ret = data[index];
        for (int i = index + 1 ; i < size ; i++)
            data [ i - 1] = data[i];
        size --;
        // data[size] = null;    // loitering objects

        // 这里等于1/4的才进行缩容，但是还要注意长度除于2不能等于0
        if (size == data.length / 4 && data.length / 2 != 0)
            resize(data.length / 2);

        return ret;
    }

​

原文  http://www.cnblogs.com/mengd/p/11515206.html
正文到此结束
所属分类： Java 编程技术

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
springboot-demo Java入门教程 bootstrap3 CSS Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 MongoDB教程 Struts2教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 Hive教程 Ant教程 ANTLR教程 SpringCloud java实例教程 springcloud-demo XStream教程 Hazelcast教程 Elastic-Job-Lite 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 solr教程 Hadoop教程 WebService CXF学习 JPA教程 ActiveMQ中文指南 java-demo Java内存模型 dubbo教程 python3-demo Linux入门视频教程
近期评论
  1. 1 Spring Cloud Consul实现选举机制
  2. 2 Spring Boot集成ShedLock实现分布式定时任务
  3. 3 利用oss进行数据库和网站图片备份
  4. 4 Spring Cloud Stream实现数据流处理
  5. 5 Python3访问MySQL数据库快速入门Demo
  6. 6 Github开源项目作者可以免费申请 JetBrains 全家桶
  7. 7 Spring Cloud Vault快速入门Demo
  8. 8 Spring Cloud Gateway快速入门Demo
  9. 9 Spring Cloud Contract快速入门Demo
  10. 10 Spring Cloud Consul快速入门Demo
网站信息
  • 文章总数：82,714 篇
  • 文件总数：284,287 个
  • 标签总数：2,393 个
  • 分类总数：85 个
  • 留言数量：2,560 条
  • 在线人数：607 人
  • 运行天数：4,409天
  • 最后更新：2024年11月22日03点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG