栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数组 java数据结构与算法(一)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数组 java数据结构与算法(一)

数据结构

研究数据如何在计算机中进行组织和存储,从而高效的获取数据和修改数据

数据结构分为三类:

线性结构:数组、队列、栈、链表、哈希表...

树型结构:二叉树、二分搜索树、AVL树、红黑树、堆、Trie、线段树、并查集...

图结构:邻接矩阵、邻接表

数组

一、数组基础

  1、数组的概念:用来存储一组相同数据类型的数据;

  2、数组在内存中分配连续的空间,数组创建时要指定容量(大小);

  3、初始化:数据类型[] 数组名  = new int[6];

             数据类型[] 数组名  = {1,2,3,4,5,6};

  4、索引--访问数组时通过索引进行操作

  5、索引从0开始,最大为array.length-1

  6、常见的数组:字符串、对象数组、哈希表

  7、空指针:nullPoint   NullPointException

  8、数组越界:outofindex   ArrayIndexOutOfBoundsException

  • 使用数组时,最重要的就是数组的索引,通过索引可以对数组进行改和查操作。

 

索引:可以有语义,也可以没有语义(理解),

            数组最好运用于索引有语义的情况;

  数组最大的优点:快速查询。

  

三、基于java中的数组,进行二次封装,制作可变数组

 

  1. 定义属于自己的数组:

 

public class MySelfArray {
    //数据容器
    private T[] data;

    //实际保存数据的个数
    private int size;

    MySelfArray(){
        this(20);
    }

    MySelfArray(int capacity){
        this.size = 0;
        data =(T[]) new Object [capacity];
    }

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

  1. 向数组中添加元素

public void addTail(T ele) {
    add(this.size,ele);
    
}


public void addHead(T ele) {
    add(0,ele);
}


public void add(int index,T ele) {
    //如果数组已满,进行扩容操作
    if(index < 0 || index > size) {
        throw new IllegalArgumentException("index is error");
    }

    if(this.size == data.length) {
        resize(2 * data.length);
    }

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

向数组尾部添加元素

 

向指定位置添加元素

 

在指定位置添加元素

 

public T remove(int index) {
    if(index < 0 || index >= size) {
        throw new IllegalArgumentException("index is invalid");
    }
    T result = data[index];
    for (int i = index + 1; i < size; i++) {
        data[i-1] = data[i];
    }
    this.size -= 1;
    data[size] = null;
    //进行缩容操作
    if(this.size == data.length / 2 && data.length / 2 > 0) {
        resize(data.length/2);
    }

    return result;
}


public T removeHead() {
    return remove(0);
}


public T removeTile() {
    return remove(this.size -1);
}


public int removeEle(T  ele) {
    int index = isContains(ele);
    if(index == -1) {
        remove(index);
    }
    return index;
}


 

删除指定位置的元素

 

更改数组的容积:

public void resize(int newCapacity) {
    T[] newData = (T[])new Object[2* data.length];
    for (int i = 0; i < this.size; i++) {
        newData[i] = data[i];
    }
    this.data = newData;
}

获取指定位置的元素:

public T getEleByIndex(int index) {
    if(index < 0 || index >= size) {
        throw new IllegalArgumentException("Index is error");
    }
    return data[index];
}

修改指定位置的元素:

public void updateByIndex(int index,T ele) {
    if(index < 0 || index >= size) {
        throw new IllegalArgumentException("Index is error");
    }
    data[index] = ele;
}

判断是否包含指定的元素内容:

public int isContains(T ele) {
    for (int i = 0; i < this.size; i++) {
        if(this.data[i].equals(ele)) {
            return i;
        }
    }
    return -1;
}

调用方法验证:

 public static void main(String[] args) {
        MySelfArray mySelfArray = new MySelfArray<>(10);

        long startTime = System.nanoTime();
        //进行添加操作
        int cout = 100;
        Random random = new Random();
        for (int i = 0; i < cout; i++) {
            mySelfArray.addTail(random.nextInt(Integer.MAX_VALUE));
        }
        System.out.println("数组" + mySelfArray);

        while(!mySelfArray.isEmpty()) {
            mySelfArray.removeTile();
        }
        long endTime = System.nanoTime();
        System.out.println("总耗时:" + (endTime - startTime)/100000000.0);

        //判断10是否存在于数组中
        System.out.println("10是否存在: " + (mySelfArray.isContains(10) == -1 ? false : true));

        MySelfArray strArray = new MySelfArray<>(5);
        strArray.addTail("apple");
        strArray.addTail("pear");
        strArray.addTail("banana");
        strArray.addTail("pineapple");
        strArray.addTail("watermelon");
        System.out.println(strArray);
        System.out.println(strArray.isContains("watermelon") == -1 ? false : true);
    }
}

练习:

package com.company.Demo01;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class MySelfArray {
    public static void main(String[] args) {

        String[] fruits = {"apple","pear","watermelon","banana","pineapple"};
        

        //Arrays.stream(fruits).forEach(System.out::println);
        //Arrays.stream(fruits).forEach(item-> System.out.println(item));

        int[] nums = new int[1000];
        Random random = new Random();
        for (int i = 0; i < 1000; i++) {
            nums[i] = random.nextInt(100000);
        }

        //1.对每个数据+10
        //2.过滤奇数
        Arrays.stream(nums).map(item->item+10).filter(item->item%2>0).forEach(System.out::println);
        

        String str = "ababccdddfghjhytrdcvv";
        //统计每个字符出现的次数(字符串中只包含小写字母)

        int[] counts = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            counts[c-'a']++;
        }
        for (int item: counts) {
            System.out.println(item);
        }
        Map map = new HashMap<>();
        
    }
}

简单的时间复杂度的分析

O(1),O(n),O(lgn),O(nlogn),O(n^2)

大O描述的是算法的运行时间和输入数据之间的关系

 

O(n)--忽略实际时间T = c1*n + c2

T = 2*n + 2          

T = 2000*n + 1000     渐进时间复杂度

T = 1*n*n + 0         描述n趋近于无穷的情况

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

·添加操作   O(n)

 

删除操作:

 

修改操作:

 

查找操作:

 

增、删、改、查

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/978466.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号