数组-动态扩容+增删改查操作+合并有序数组

57 阅读 0 评论 38 点赞

我是靠谱客的博主勤劳招牌，最近开发中收集的这篇文章主要介绍数组-动态扩容+增删改查操作+合并有序数组，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这一篇我们来主要演示数组相关的练习，这里主要涉及数组的动态扩容、数组的增删改查操作以及合并两个原本有序的数组为一个新数组。

数组动态扩容

需求：支持数组的尾部插入、按照index位置插入，当数组容量满后将数组扩容为原来的两倍，并迁移原来的数组数据到新的数组中。这里我将数组的增删查改操作和数组的扩容放到一个代码中。

package com.study.algorithm.array;

/**
 * @Auther: JeffSheng
 * @Date: 2019/8/21 10:33
 * @Description: 实现一个动态扩容的数组和数组元素的增删查改
 */
public class DynamicArray {

    private String[] array = null;

    //数组的容量
    private int capacity = 0;

    //数组中元素个数
    private int count=0;

    public DynamicArray(int capacity){
        this.array = new String[capacity];
        this.capacity = capacity;
    }

    /**
     * 插入数据的过程中(插入到数组尾巴)，数组动态扩容
     * @param item
     * @return
     */
    public boolean insert(String item){
        //数组满了，扩大容量到二倍
        if(count==capacity){
            //数据搬移
            resize();
        }
        array[count]=item;
        count++;
        return true;
    }


    public boolean insert(int index,String item){
        if(index < 0 || index > count){
            return  false;
        }
        if(count==capacity){
            resize();
        }
        for (int i = count - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }
        array[index] = item;
        count++;
        return true;
    }

    private void resize() {
        //数据搬移
        capacity = capacity*2;
        String[] newArray = new String[capacity];
        for (int i=0; i < count;i++){
            newArray[i] = array[i];
        }
        this.array = newArray;
    }


    /**
     * 根据索引删除数组中的元素
     * @param index
     * @return
     */
    public boolean delete(int index){
        if(index <0 || index >=count){
            return false;
        }
        //从删除位置开始，将后面的元素向前移动一位
        for (int i=index+1; i<= count; i++){
            array[i-1]=array[i];
        }
        count--;
        return true;
    }

    //根据索引，找到数据中的元素并返回
    public String find(int index){
        if (index < 0 || index >= count) return null;
        return array[index];
    }


    // 修改 index 位置的元素
    public boolean set(int index, String item) {
        if (index < 0 || index >= count) return false;
        array[index] = item;
        return true;
    }

    // 查看数组是否包含元素item
    public boolean contains(String item) {
        for (int i = 0; i < count; i++) {
            if (array[i].equals(item)) {
                return true;
            }
        }
        return false;
    }

    public void printAll(){
        for (int i=0; i < capacity;i++){
            System.out.print("["+array[i]+"]");
        }
        System.out.println("------");
    }

    public static void main(String[] args) {
        DynamicArray dynamicArray = new DynamicArray(5);
        dynamicArray.insert("a");
        dynamicArray.insert("b");
        dynamicArray.insert("c");
        dynamicArray.insert("d");
        dynamicArray.insert("e");
        dynamicArray.printAll();
        dynamicArray.insert("f");
        dynamicArray.printAll();

        System.out.println("-----------找到的元素为：-----"+dynamicArray.find(3));
        if(dynamicArray.delete(3)){
            dynamicArray.printAll();
        }else{
            System.out.println("删除的位置非法..");
        }
        dynamicArray.insert(3,"d");
        dynamicArray.printAll();
        if(dynamicArray.contains("e")){
            System.out.println("数组中包含元素:e");
        }
    }
}

合并两个有序数组

需求：合并两个有序数组为一个新的数组。比如数组a：{1,2,4},b:{1,3,4,5},合并后的新数组为{1,2,3,4,4,5}.

这里先把代码发出来，这里是参考leedcode上一个写的很棒的算法：一次循环即可搞定合并，时间复杂度O(m+n)。

package com.study.algorithm.array;
/**
 * @author JeffSheng
 * @Date: 2019/8/21 15:04
 * @Description: 合并两个有序数组为一个有序数组
 */
public class MergeSortArray{

    public static int[] mergeSortArr(int[] arrA, int[] arrB){
        int m = arrA.length;
        int n = arrB.length;
        int k = m+n-1;
        int[] newArr = new int[k+1];
        for(int i = m-1,j = n-1;k >= 0;k--)
        {
            if(i < 0)
            {
                newArr[k] = arrB[j--];
                continue;
            }
            if(j < 0)
            {
                newArr[k] = arrA[i--];
                continue;
            }

            if(arrA[i] >= arrB[j])
                newArr[k] = arrA[i--];
            else
                newArr[k] = arrB[j--];
        }
        return newArr;
    }

    public static void main(String[] args) {
        int[] arrA = {1,2,4};
        int[] arrB = {1,3,4,5};
        int[] newArr = mergeSortArr(arrA,arrB);
        for (int i = 0; i < newArr.length; i++) {
            System.out.print("["+newArr[i]+"]");
        }
    }

}

思想：从两个待合并的数组尾巴开始，比较大小，将较大的一个存储到新数组的尾巴。为了清楚模拟这个过程，方便理解，这里我画了个图：