• 02-数组(Array)应用分析

    文章目录

    数组(Array)应用分析

    什么是数组？

    数组是一个有限的、类型相同的数据的集合，在内存中是一段连续的内存区域，这段内存区域一旦定义，其大小不改变。
    在这里插入图片描述

    数组的长度在定义时确定，数组中的元素的默认值由其数组类型决定。可通过数组下标访问数组中元素，下标的起始位置永远从0开始。

    如何查找数组中元素？

    数组在访问操作方面有着独特的性能优势，因为数组不仅仅支持顺序访问，还支持随机访问，如图所示。
    在这里插入图片描述
    我们可以通过下标随机访问数组中任何一个元素，其原理是因为数组中元素的存储是连续的，所以我们可以通过数组内存空间的首地址加上元素的偏移量计算出某一个元素的内存地址，例如，array[n]的地址 = array数组内存空间的首地址 + 每个元素大小*n。
    构建一个长度为5的整数数组int[]array=new int[5],在内存中会开辟一块连续的内容空间，假设其首地址为2000，其它元素的地址表示，如图所示。

    在这里插入图片描述

    总之，当我们通过下标去访问数组中的数据时，并不需要从头开始依次遍历数组，因此数组的访问时间复杂度是 O(1)，当然这里需要注意，如果不是通过下标去访问，而是通过内容去查找数组中的元素，则时间复杂度不是O(1)，极端的情况下需要遍历整个数组的元素，时间复杂度可能是O(n)，当然通过不同的查找算法所需的时间复杂度是不一样的。

    如何实现数组中数据的插入和删除？

    数组元素的连续性，导致数组在插入和删除元素的时候效率比较低。如果要在数组中间插入一个新元素，就必须要将要相邻的后面的元素全部往后移动一个位置，留出空位给这个新元素，如图所示。
    在这里插入图片描述
    数组插入时，首先要检测数组中是否有足够的空间可以存储新的元素，假如不足还需要对数组进行扩容。一般会重新申请一个相对原数组1.5倍大小的存储空间（因为数组在内存中是一块连续的内存空间，一旦定义其长度不可以再进行修改），并且把原来的数据拷贝到新申请的空间上。假如现在数组空间是足够的，新元素要插入在数组的最开头位置，那整个原始数组都需要向后移动一位，此时的时间复杂度为最坏情况即O(n)，如果新元素要插入的位置是最末尾，则无需其它元素移动，则此时时间复杂度为最好情况即O(1)，所以平均而言数组插入的时间复杂度是O(n)。

    Java中数组插入操作，其代码示例如下：

    // function to search a key to  
// be deleted 
static int findElement(int arr[], int n, int key) {
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == key)
            return i;

    return -1;
}

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

    数组的删除与插入类似，假如不是删除最后一个有效元素，其它元素在删除以后，后续元素都要向前移动，如图-5所示：

    在这里插入图片描述

    图-5
    数组删除时，如果删除数组末尾的数据，则最好情况时间复杂度为O(1)。如果删除开头的数据，则最坏情况时间复杂度为O(n)。所以平均情况时间复杂度也为O(n)。Java中的数组删除操作，其实现代码如下：

    // function to search a key to  
// be deleted 
static int findElement(int arr[], int n, int key) {
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == key)
            return i;

    return -1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
        // Function to delete an element 
    static int deleteElement(int arr[], int n, int key)  {
        // Find position of element to be  
        // deleted 
        int pos = findElement(arr, n, key);

        if (pos == -1)
        {
            System.out.println("Element not found");
            return n;
        }

        // Deleting element 
        int i;
        for (i = pos; i< n - 1; i++)
            arr[i] = arr[i + 1];

        return n -1;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    JAVA中手写简易ArrayList容器？

    public class SimpleArrayContainer {

    private Object[] array;
    private int size;
    public SimpleArrayContainer() {
        this(10);
    }
    public SimpleArrayContainer(int capacity) {
        this.array=new Object[capacity];
    }

    private Object[] copyOf(Object[] source,int length) {
        //1)创建新数组，并定义其长度为原数组的2倍大小
        Object[] newArray=new Object[2*length];
        //2)拷贝原有数组内容到新数组
        for(int i=0;i<source.length;i++) {
            newArray[i]=source[i];
        }
        //3)返回新创建的数组
        return newArray;
    }
    //定义向数组size位置添加新元素的方法
    public void add(Object element) {
        //1.数组是否已满了，满了则扩容
        if(size==array.length) {
            //array=copyOf(array, 2*array.length);
            array=Arrays.copyOf(array, 2*array.length);
        }
        //2.添加新的元素
        array[size++]=element;
    }
    //定义在指定位置添加新的元素的方法
    public void add(int index,Object element) {
        if(index<0||index>size)
            throw new IndexOutOfBoundsException();
        if(size==array.length) {
            array=Arrays.copyOf(array, 2*array.length);
        }
        System.arraycopy(array, index, array, index+1, size-index);
        array[index]=element;
        size++;
    }
    //定义按指定位置删除数组元素的方法
    public Object remove(int index) {
        //1.参数校验
        if(index<0||index>=size)
            throw new IndexOutOfBoundsException();
        //2.获取index位置元素
        Object element=array[index];
        //3.移动元素
//    int numMoved=size-index-1;
//    if(numMoved>0)
//    System.arraycopy(array, index+1, array, index, numMoved);
//    //4.修改最后一个元素的值，并且有效元素个数减1
//    this.array[--size]=null;
        fastRemove(index);
        return element;
    }
    private void fastRemove(int index) {
        int numMoved=size-index-1;
        if(numMoved>0)
            System.arraycopy(array, index+1, array, index, numMoved);
        array[--size]=null;
    }
    //按元素值移除元素
    public boolean remove(Object element) {
        if(element==null) {
            for(int index=0;index<size;index++) {
                if(array[index]==null) {
                    //移除元素
                    fastRemove(index);
                    return true;
                }
            }
        }else {
            for(int index=0;index<size;index++) {
                if(array[index].equals(element)) {
                    //移除元素
                    fastRemove(index);
                    return true;
                }
            }

        }
        return false;
    }

    public Object get(int index) {
        if(index<0||index>=size)
            throw new IndexOutOfBoundsException();
        return this.array[index];
    }

    @Override
    public String toString() {
        return Arrays.toString(array);
    }
    public int size() {
        return size;
    }
    public static void main(String[] args) {
        SimpleArrayContainer container=new SimpleArrayContainer(2);
        container.add(100);//size
        container.add(200);
        container.add(300);
        System.out.println(container);//[100,200,300]
        container.add(1, 400);
        System.out.println(container);//[100,400,200,300]
        container.remove(1);
        System.out.println(container);//[100,200,300]
        container.remove((Object)200);
        System.out.println(container);//[100,300]
        Object element=container.get(0);
        System.out.println(element);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116

    基于JAVA如何实现数组元素的旋转？

    初始数组为Input,然后向左旋转数组实现Output数组结果

    Input :  arr[] = [1, 2, 3, 4, 5, 6, 7]

rotate Left

Output : arr[] = [3, 4, 5, 6, 7, 1, 2]

    • 1
    • 2
    • 3
    • 4
    • 5

    初始数组为Input,然后向右旋转数组实现Output数组结果

    Input :  arr[] = [1, 2, 3, 4, 5, 6, 7]

rotate right

Output : arr[] = [6, 7, 1, 2, 3, 4, 5]

    • 1
    • 2
    • 3
    • 4
    • 5

    具体实现方案如下：

    package com.cy.pj.ds.array;

import java.util.Arrays;

public class RotateLeftArray {

//左转方案1：时间复杂度为O(n),辅助空间复杂度为O(count)
    static void doRotateLeft01(int[] source,int count) {
        //1.构建临时数组，用于存储需要移动数组右边的元素
        int[] temp=new int[count];
        for(int i=0;i<temp.length;i++) {//空间复杂度 S=O[count]
            temp[i]=source[i];
        }
        //2.移动source数组中剩余元素
        for(int i=count;i<source.length;i++) {//时间复杂度 t=O[n]
            source[i-count]=source[i];
        }
        //3.将temp数组中的元素存储到source数组
        for(int i=0;i<temp.length;i++) {
            source[source.length-(count-i)]=temp[i];
        }
    }

//左转方案2：时间复杂度O(n*count)，辅助空间O(1)
    //分多次移动数组元素
    //[1,2,3,4,5,6,7]
    //[2,3,4,5,6,7,1]
    //[3,4,5,6,7,1,2]
    static void doRotateLeft02(int[] source,int count) {
        for(int i=0;i<count;i++) {//外层循环控制移动次数，T=O(n*count)
            int temp=source[0],j;//空间复杂度,S=O(1)
            for(j=0;j<source.length-1;j++) {//移动元素的个数
                source[j]=source[j+1];
            }
            source[j]=temp;
        }
    }
    //右转方案1：时间复杂度为O(n*count)，辅助空间为O(1)
    static void doRotateRight01(int[] source,int count) {
        int len=source.length-1;
        for(int i=0;i<count;i++) {
            int temp=source[len],j;
            for(j=len;j>0;j--) {
                source[j]=source[j-1];
            }
            source[j]=temp;
        }
    }

    public static void main(String[] args) {
        //rotate left
        //intput:[1,2,3,4,5,6,7]
        //rotate left
        //output:[3,4,5,6,7,1,2]
        int[] source= {1,2,3,4,5,6,7};
        //doRotateLeft01(source,2);
        //doRotateLeft02(source,2);

        //rotate right
        //intput:[1,2,3,4,5,6,7]
        //rotate right
        //output:[6,7,1,2,3,4,5]

        doRotateRight01(source, 2);
        System.out.println(Arrays.toString(source));

    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    基于JAVA实现有序数组的二分查找操作？

    static int binarySearch(int arr[],
                        int low, int high, int key)
{
    if (high < low)
        return -1;

    /* low + (high - low)/2; */
    int mid = (low + high)/2;
    if (key == arr[mid])
        return mid;
    if (key > arr[mid])
        return binarySearch(arr, (mid + 1), high, key);
    return binarySearch(arr, low, (mid -1), key);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    数组的优势和劣势是什么？

    数组连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以数据也就具备了很好的“随机访问”的性能。但有利就有弊，这个限制也让数组的很多操作变得非常低效。例如，数组中删除、插入一个数据时，为了保证连续性，就需要做大量的数据移动操作。

    总结(Summary)

  • 相关阅读:
    游戏滚动列表的优化（降低drawcall从154降低到14，图片大小，界面逻辑）
    src实战-两处nacos未授权访问
    Leetcode-每日一题792. 匹配子序列的单词数（分桶）
    Qt设置整体背景颜色
    string转float显示位数有误；cout 的 precision 成员函数
    .net6 WebApi 如何将变量注入到控制器 以及配置文件的读取
    MyBatis面试题(二)
    开源协助平台工程灵活应对多云时代的挑战
    ＜el-date-picker＞ 设置默认yyyy-MM-dd以及限制规则
    MATLAB2016笔记（六）：数据可视化
  • 原文地址：https://blog.csdn.net/maitian_2008/article/details/127564370