JaStE   发表于 2020-1-21 23:05:35 |栏目:






当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。
稀疏数组(sparsearray)的处理方式:

记录数组一共有几行几列,有多少个不同的值
把具有不同值的元素的行列以及值记录在一个小规模的数组中,从而缩小程序的规模。

二维数组转稀疏数组的思路

遍历原始的二维数组,得到有效数据(不同的值的数据)的个数sum
根据sum可以创建稀疏数组sparseArray int[sum+1][3]
将二维数组的行列以及sum写入数组的第一行。然后将二维数组的有效数据存入到稀疏数组。

代码实现:
/**
     * 将二维数组转为稀疏数组
     * @param twoDimensional
     */
    private static int[][] twoDimensionalToSparseArray(int[][] twoDimensional){
        if(twoDimensional.length == 0){
            return null;
        }
        //遍历得到二维数组一共有多少不同的值
        int sum = 0;
        for(int[] array : twoDimensional){
            for(int value : array){
                if(value != 0){
                    sum++;
                }
            }
        }

        //创建稀疏数组
        int[][] sparseArray = new int[sum+1][3];

        //首先保存第一行数据(二维数组的行、列、多少个不同的值)
        sparseArray[0][0] = twoDimensional.length;
        sparseArray[0][1] = twoDimensional[0].length;
        sparseArray[0][2] = sum;

        //遍历二维数组,将不同的值存入稀疏数组
        int count = 0;
        for(int i = 0; i < twoDimensional.length;i++){
            for(int j = 0; j < twoDimensional[0].length; j++){
                if(twoDimensional[j] != 0){
                    //先做加1操作,因为第一行保存了二维数组的行列信息
                    count++;
                    //保存行
                    sparseArray[count][0] = i;
                    //保存列
                    sparseArray[count][1] = j;
                    //保存值
                    sparseArray[count][2] = twoDimensional[j];
                }
            }
        }
        return sparseArray;
    }

    private static void printArray(int[][] array){
        for(int[] arr : array){
            for(int a : arr){
                System.out.print(a+"  ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        //构造二维数组
        //构造一个11*11的二维数组,且第一行第二列为1,第二行第三列为2
        int[][] twoDimensional = new int[11][11];
        twoDimensional[0][1] = 1;
        twoDimensional[1][2] = 2;

        //打印原始二维数组
        System.out.println("原始二维数组");
        printArray(twoDimensional);
        System.out.println();

        //将二维数组转为稀疏数组并且打印
        int[][] sparseArray = twoDimensionalToSparseArray(twoDimensional);
        System.out.println("稀疏数组");
        printArray(sparseArray);


    }
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
稀疏数组转二维数组思路

先读取稀疏数组的第一行,根据第一行的数据(行和列)创建二维数组。
在读取稀疏数组后面几行的内容,依次赋值给二维数组即可。

代码实现
/**
     * 将稀疏数组转为二维数组
     * @param sparseArray
     * @return
     */
    private static int[][] sparseArrayToTwoDimensional(int[][] sparseArray){
        if(sparseArray.length == 0){
            return null;
        }
        //读取稀疏数组的第一行构造二维数组
        //行
        int row = sparseArray[0][0];
        int column = sparseArray[0][1];
        int[][] twoDimensional = new int[row][column];

        //读取稀疏数组剩余部分,循环给二维数组赋值
        for(int i = 1; i < sparseArray.length; i++){
            twoDimensional[sparseArray[0]][sparseArray[1]] = sparseArray[2];
        }

        return twoDimensional;
    }
   
   
     public static void main(String[] args) {
        //构造二维数组
        //构造一个11*11的二维数组,且第一行第二列为1,第二行第三列为2
        int[][] twoDimensional = new int[11][11];
        twoDimensional[0][1] = 1;
        twoDimensional[1][2] = 2;

        //打印原始二维数组
        System.out.println("原始二维数组");
        printArray(twoDimensional);

        //将二维数组转为稀疏数组并且打印
        int[][] sparseArray = twoDimensionalToSparseArray(twoDimensional);
        System.out.println("稀疏数组");
        printArray(sparseArray);

        int[][] newTwoDimensional = sparseArrayToTwoDimensional(sparseArray);
        System.out.println("还原后的二维数组");
        printArray(newTwoDimensional);

    }
123456789101112131415161718192021222324252627282930313233343536373839404142434445

队列是一个有序列表,可以使用数组或者链表来实现
遵循先入先出原则。即先存入队列的数据,要先取出,后存入队列的数据要后取出。


队列本身是有序列表,若使用数组的结构来存储队列的数据,因为队列的输出输入是分别从前后端来处理,因此需要两个变量front及rear分别表示队列前后端的下标。front会随着数据的输出二改变,rear会随着数据的输入而改变。

代码实现如下:

对数组模拟队列的优化,充分利用数组,因此将数组看做是一个环形的(通过取模的方式来实现)
思路分析:

front 变量的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素。
rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间做为约定。
当队列满时,条件时(rear+1)%maxSize=front [满]
当队列为空的条件:rear == front 空
队列中的有效数据个数(rear+maxSize-front)%maxSize // rear=1 front=0

尾索引的下一个为头索引表示队列满
代码实现
public class MyQueue {
    //表示队列的数组
    private int[] queue;
    //头部下标
    private int head;
    //尾部下标
    private int tail;

    public MyQueue(int n) {
        queue = new int[n];
        head = -1;
        tail = -1;
    }

    /**
     * 判断队列为空
     *
     * @return:
     * @author: zhaojiaxing
     * @createTime: 2019/10/31 0031 22:02
     */
    public boolean isEmpty() {
        return head == tail ? true : false;
    }

    /**
     * 判断队列是否已满
     *
     * @return:
     * @author: zhaojiaxing
     * @createTime: 2019/10/31 0031 22:04
     */
    public boolean isFull() {
        if (head >= queue.length - 1) {
            return true;
        }
        return false;
    }

    /**
     * 向队列中放元素
     *
     * @param num
     * @return: int
     * @author: zhaojiaxing
     * @createTime: 2019/10/31 0031 22:12
     */
    public int add(int num) {
        if (isFull()) {
            throw new RuntimeException("队列已满,不能再添加元素");
        }
        head++;
        queue[head] = num;
        return queue[head];
    }

    /**
     * 向队列中取元素
     * @param
     * @return: int
     * @author: zhaojiaxing
     * @createTime: 2019/10/31 0031 22:15
     */
    public int get() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空,不能再获取元素");
        }
        tail++;
        return queue[tail];
    }

    /**
     * 打印队列
     * @return:
     * @author: zhaojiaxing
     * @createTime: 2019/10/31 0031 22:20
     */
    public void searchQueue(){
        if(isEmpty()){
            System.out.println("队列 为空");
        }
        for(int i = tail+1;i<=head;i++){
            System.out.print(queue+" ");
        }
        System.out.println(" ");
    }

    public static void main(String[] args) {
        //初始化队列
        MyQueue queue = new MyQueue(10);
        //向队列中添加元素
        try {
            for(int i = 0;i < 12;i++){
                queue.add((int)((Math.random()+1)*20));
            }
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        queue.searchQueue();

        //从队列中读取元素
        try {
            System.out.println("向队列中获取元素");
            for(int i = 0;i < 12;i++) {
                System.out.println(queue.get());
            }
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        queue.searchQueue();
    }
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112

回复 显示全部楼层 使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

作者相关信息

更多资源

精品推荐

极品资源

原创模板

下载排行

热门标签

快速回复 返回顶部 返回列表