不要小瞧数组

程序员文章站 2022-07-28 19:07:27

一、使用java中的数组数组：把数据码成一排进行存放在元素前面添加一个新元素四、数组中查询元素和修改元素还是在上面的类中写方法，这里重写toString方法，用于查询元素把前面写的功能进行测试说明还是成功的，由于int类型太单调，之后都将使用泛型来进行操作七、动态数组由于数组是由限制 ......

一、使用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]

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

六、使用泛型

让我们的数据结构可以放置任何的数据类型
不可以是基本数据类型，只能是类对象：boolean、byte、chat、short、int、long、float、double
每个基本数据类型都有对应的包装类：boolean、byte、chat、short、int、long、float、double
下面还是针对上面的进行修改，由于使用了泛型，这里将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]

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

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

o(1)，o(n)，o(lgn)，o(nlogn)，o(n^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中的个数越多时间就越多

为什么要用大o，叫做o(n)？忽略常数，实际时间(线性)
$$
t = c1*n + c2
$$

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

t = 2*n + 2	o(n)
t = 2000*n + 1000	o(n)
t = nn1 + 0	o(n^2)
t = 2nn + 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方法？

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

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)

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

均摊复杂度

addlast的均摊复杂度是o(1)

同理，removelast的均摊复杂度也是o(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;
    }

上一篇：并发编程之多线程

下一篇：你选的那些创业方向可能正在毁掉你！

不要小瞧数组

一、使用java中的数组

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

三、向数组添加元素

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

五、包含，搜索和删除

六、使用泛型

七、动态数组

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

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

笔记本最好不要使用屏保

linux awk 数组排序多种实现方法

浅谈Java数组的一些使用方法及堆栈存储

php数组中包含中文的排序方法

PHP二维数组排序简单实现方法

PHP使用array_merge重新排列数组下标的方法

C#byte数组与Image的相互转换实例代码

Javascript数组方法reduce的妙用之处分享

JavaScript之数组reduce()和reduceRight()方法学习讲解

C#基础之数组排序、对象大小比较实现代码