01--图解数据结构之数组实现集合

数组是一种线性的数据结构 优点:定点查询--速度快 缺点:长度固定,操作不便 注:集合的基类见第一篇:图解数据结构之开篇+集合基类

一个数组.png


一、java数组的使用

/**
 * 作者:张风捷特烈
 * 时间:2018/9/19 0019:8:59
 * 邮箱:1981462002@qq.com
 * 说明:数组测试
 */
public class ClientOfArray {

    public static void main(String[] args) {
        //生成数组--方式1
        int[] id = new int[5];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }

        //生成数组--方式2
        String[] name = new String[]{"张", "风", "捷", "特", "烈"};
        for (int i = 0; i < name.length; i++) {
            System.out.print(name[i]);//张风捷特烈
        }
        //增强for循环
        for (String str : name) {
            System.out.print(str);//张风捷特烈
        }
    }
}

二、自定义数组:ArrayGroup

1.成员及构造
/**
 * 成员数组
 */
private T[] datas;

/**
 * 无参构造--默认容量10
 */
public ArrayGroup() {
    this(10);
}

/**
 * 一参构造
 * @param capacity 集合容量
 */
public ArrayGroup(int capacity) {
    //实例化数组
    datas = (T[]) new Object[capacity];
}

 @Override
 public String toString() {
     StringBuilder sb = new StringBuilder();
     sb.append(String.format("ArrayGroup:size =%d,capacity=%d\n",size,datas.length));
     sb.append("[");
     for (int i = 0; i < size; i++) {
         sb.append(datas[i].toString());
         if (i != size - 1) {
             sb.append(", ");
         }
     }
     sb.append("]");
2.定点添加元素:

思路:定点后的所有元素后移一位,空出顶点位,让待添加元素入驻

数组定点添加.png

添加方法实现:
@Override
public void add(int index, T el) {
    if (size == datas.length) {
        throw new IllegalArgumentException("Add failed! Array is full");
    }
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Add failed! Make sure index < 0 || index > size");
    }
    //从最后一个元素开始,到定点位置元素,后移一位
    for (int i = size-1; i >=index ; i--) {
        datas[i + 1] = datas[i];
    }
    datas[index] = el;
    size++;
}
添加方法测试:
 ArrayGroup<String> arrayGroup = new ArrayGroup<>();
 arrayGroup.addLast("风");
 arrayGroup.addLast("特");
 arrayGroup.addLast("烈");
 arrayGroup.add(1,"捷");
 arrayGroup.addFirst("张");
 System.out.println(arrayGroup);
 //ArrayGroup:size =5,capacity=10
 //[张, 风, 捷, 特, 烈]

3.查找

定点查找

@Override
public T get(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("Get failed! Make sure index < 0 || index > size");
    }
    return datas[index];
}

定元素查找

 @Override
 public int[] getIndex(T el) {
     //临时数组
     int[] tempArray = new int[size];
     //重复个数
     int count = 0;
     //遍历集合,获取该元素重复个数,及位置数组
     for (int i = 0; i < size; i++) {
         if (datas[i].equals(el)) {
             tempArray[count] = i;
             count++;
         }
     }
     //将临时数组压缩
     int[] indexArray = new int[count];
     for (int i = 0; i < count; i++) {
         indexArray[i] = tempArray[i];
     }
     return indexArray;
 }

4.定点设置
 @Override
 public T set(int index, T el) {
     if (index < 0 || index >= size) {
         throw new IllegalArgumentException("Set failed! Make sure index < 0 || index > size");
     }
     T oldEl = get(index);
     datas[index] = el;
     return oldEl;
 }

5.定点移除

思路:从删除元素索引的下一位开始到结尾,依次左移

数组定点移除.png

@Override
public T remove(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("Remove failed! Make sure index < 0 || index > size");
    }
    T temp = get(index);
    //从删除元素索引的下一位开始到结尾,依次左移
    for (int i = index + 1; i < size; i++) {
        datas[i - 1] = datas[i];
    }
    size--;
    //置空--游荡的对象
    datas[size] = null;
    return temp;
}

6.清空

这里要注意一点,从后往前删除。因为从头删,每次后面都要全部移位,消耗很大。 正向10W数据清空:正向clear:方法耗时:10.549秒 逆向100W数据清空:耗时0,可见天壤之别。所以一个好的算法作用是很大的

@Override
public void clear() {
    for (int i = size-1; i <= 0; i--) {
        remove(i);
    }
    size = 0;
}

7.定点插入集合
@Override
public Group<T> contact(int index, Group<T> group) {
    //从index处遍历本数组,将待插入数据一个一个插入
    for (int i = index; i < index+group.size(); i++) {
        add(i+1, group.get(i-index));
    }
    return this;
}

三、测试

    private static void otherTest(ArrayGroup<String> arrayGroup) {
        arrayGroup.addLast("a");
        arrayGroup.addLast("a");
        arrayGroup.addLast("b");
        arrayGroup.addLast("c");
        arrayGroup.addLast("f");
        arrayGroup.addLast("a");
        arrayGroup.addLast("e");
        arrayGroup.addLast("d");

        System.out.println(arrayGroup);
        //ArrayGroup:size =8,capacity=10
        //[a, a, b, c, f, a, e, d]

        //定点删除操作
        String remove = arrayGroup.remove(3);
        System.out.println(remove);//c
        System.out.println(arrayGroup);
        //ArrayGroup:size =7,capacity=10
        //[a, a, b, f, a, e, d]

        //定元素删除
        int a = arrayGroup.removeEl("a");
        System.out.println(a);//0
        System.out.println(arrayGroup);
        //ArrayGroup:size =6,capacity=10
        //[a, b, f, a, e, d]

        //定元素全删除
        boolean ok = arrayGroup.removeEls("a");
        System.out.println(ok);//true
        System.out.println(arrayGroup);
        //ArrayGroup:size =4,capacity=10
        //[b, f, e, d]

        //定点修改
        String toly = arrayGroup.set(3, "toly");
        System.out.println(toly);//d
        System.out.println(arrayGroup);
        //ArrayGroup:size =4,capacity=10
        //[b, f, e, toly]

        //是否存在元素
        boolean contains = arrayGroup.contains("b");
        System.out.println(contains);//true

        //定点插入集合
        ArrayGroup<String> arrayGroup2 = new ArrayGroup<>();
        arrayGroup2.addLast("1");
        arrayGroup2.addLast("2");
        arrayGroup.contact(2,arrayGroup2);
        System.out.println(arrayGroup);
        //ArrayGroup:size =6,capacity=10
        //[b, f, e, 1, 2, toly]

        //末尾插入集合
        arrayGroup.contact(arrayGroup2);
        System.out.println(arrayGroup);
        //ArrayGroup:size =8,capacity=10
        //[b, f, e, 1, 2, toly, 1, 2]
        
        //清空
        arrayGroup.clear();
        System.out.println(arrayGroup);
        //ArrayGroup:size =0,capacity=10
        //[]
    }

四、动态数组:

1、扩容方法
/**
 * 扩容 
 *
 * @param newCapacity 新容量
 */
private void grow(int newCapacity) {
    T[] newData = (T[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newData[i] = datas[i];
    }
    datas = newData;
}
2、添加满了扩容
 @Override
 public void add(int index, T el) {
     if (size == datas.length) {
         grow((int) (GROW_RATE * datas.length));
     }
3、移除元素后,动态修改总容量
 //缩容
 if (size == datas.length /4 && datas.length/2 !=0){
     grow(datas.length /2);
 }

五、测试ArrayGroup:

方法\数量

复杂度

1000次

10000次

10W次

100W次

1000W次

1亿次

addLast

O(1)

0.0秒

0.0秒

0.0秒

0.0秒

0.0秒

0.0秒

addFirst

O(n)

0.0秒

0.0秒

0.006秒

0.021秒

0.142秒

1.194秒

add

O(n)

--

--

--

--

--

--

removeLast

O(1)

0.0秒

0.0秒

0.0秒

0.0秒

0.0秒

0.0秒

removeFirst

O(n)

0.0秒

0.001秒

0.003秒

0.018秒

0.143秒

1.18秒

removeEl

O(n)

--

--

--

--

--

--

removeEls

O(n)

--

--

--

--

--

--

remove

O(n)

--

--

--

--

--

--

clear

O(1)

0.0秒

0.0秒

0.0秒

0.0秒

0.0秒

0.0秒

set

O(1)

--

--

--

--

--

--

get

O(1)

--

--

--

--

--

--

getIndex

O(n)

--

--

--

--

--

--


后记、

1.声明:

[1]本文由张风捷特烈原创,各图均由本人亲自所画,转载请注明 [2]欢迎广大编程爱好者共同交流 [3]个人能力有限,如有不正之处欢迎大家批评指证,必定虚心改正 [4]你的喜欢与支持将是我最大的动力

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Danny的专栏

探秘static——类不需实例化就能用?

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

1064
来自专栏搞前端的李蚊子

JS实现一个v-if

933
来自专栏java 成神之路

java.lang.Void 解析与使用

2865
来自专栏计算机视觉与深度学习基础

Leetcode 224. Basic Calculator

Implement a basic calculator to evaluate a simple expression string. The expre...

2377
来自专栏个人分享

Scala第一章学习笔记

  面向对象编程是一种自顶向下的程序设计方法。用面向对象方法构造软件时,我们将代码以名词(对象)做切割,每个对象有某种形式的表示服(self/this)、行为(...

1062
来自专栏武培轩的专栏

剑指Offer-不用加减乘除做加法

package Other; /** * 不用加减乘除做加法 * 写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。 * 思...

2635
来自专栏专注 Java 基础分享

从源码解析LinkedList集合

     上篇文章我们介绍了ArrayList类的基本的使用及其内部的一些方法的实现原理,但是这种集合类型虽然可以随机访问数据,但是如果需要删除中间的元素就...

2025
来自专栏尾尾部落

[剑指offer] 栈的压入、弹出序列 [剑指offer] 栈的压入、弹出序列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序...

1032
来自专栏java初学

java — 值传递和引用传递

3929
来自专栏androidBlog

笔试题—字符串常见的算法题集锦

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

1441

扫码关注云+社区

领取腾讯云代金券