java多维数组的使用与简易算法

java初级编程

多维数组的使用

练习1

练习1
/*
 * 或许arr数组中所有元素的和
 * 使用for的嵌套循环
 */
public class ArrayExer1 {
    
    public static void main(String[] args) {
        int[][] arr = new int[][]{{3,5,8},{12,9},{7,0,6,4}};
        
        int sum = 0;//记录总和
        for(int i = 0;i < arr.length;i++){
            for(int j = 0;j < arr[i].length;j++){
                sum += arr[i][j];
            }
        }
        
        System.out.println("总和为：" + sum);
    }
    
}

练习2

==int[] x,y[]==

  • x定义为一维数组；y是二维数组；int[]x;int[]y[]
+ 一维数组赋值：int[] x 或者int x[]
+ 二维数组赋值：int[][]y 或  者 int[] y[] 或者 int y[][]

//以下是否能通过编译
+ x[0] = y;  no
+ y[0] = x;  yes
+ y[0][0] = x;  no
+ x[0][0] = y;  no
+ y[0][0] = x[0]; yes
+ x = y;  no

练习3

  • 使用二维数组打印一个10行杨辉三角
    • 第一行有1个元素，第n行有n个元素
    • 每一行的第一个元素和最后一个元素都是1
    • 从第三行开始，对于非第一个元素和最后一个元素的元素。即：
yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];

/*
 * 使用二维数组打印一个 10 行杨辉三角。

【提示】
 1. 第一行有 1 个元素, 第 n 行有 n 个元素
 2. 每一行的第一个元素和最后一个元素都是 1
 3. 从第三行开始, 对于非第一个元素和最后一个元素的元素。即：
yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
 * 
 */
public class YangHuiTest {
    
    public static void main(String[] args) {
        //1.声明并初始化二维数组
        int[][] yangHui = new int[10][];
        
        //2.给数组的元素赋值
        for(int i = 0;i < yangHui.length;i++){
            yangHui[i] = new int[i + 1];
            
            //2.1 给首末元素赋值
            yangHui[i][0] = yangHui[i][i] = 1;
            //2.2 给每行的非首末元素赋值
            //if(i > 1){
            for(int j = 1;j < yangHui[i].length - 1;j++){
                yangHui[i][j] = yangHui[i-1][j-1] + yangHui[i-1][j];
            }
            //}
        }
        
        
        //3.遍历二维数组
        for(int i = 0;i < yangHui.length;i++){
            for(int j = 0;j < yangHui[i].length;j++){
                System.out.print(yangHui[i][j] + "  ");
            }
            System.out.println();
        }
        
        
        
    }
    
    
}

数组中涉及到的常见的算法题

  • 数组元素的赋值（杨辉三角、回形数等）
  • 求数值型数组中元素的最大值、最小值、平均数、总和等
  • 数组的复制、反转、查找（线性查找、二分法）
  • 数组元素的排序算法

练习一

创建一个长度为6的int型数组，要求数组元素的值都在1-30之间，且是随机赋值。同时，要求元素的值各不相同。

public class ArrayExer3 {
    public static void main(String[] args){
        int[] arr = new int[6];
        for (int i = 0; i < arr.length; i++){
//          公式：Math.random()*(n-m)+m，生成大于等于m小于n的随机数；
            arr[i] = (int)(Math.random()*30 + 1);
            boolean judgement = true;
            while(true){
                for (int j = 0;j < i;j++){
                    if (arr[j] == arr[i]){
                        judgement = true;
                        break;
                    }
                }   
                if (judgement){
                    arr[i] = (int)(Math.random()*30 + 1); 
                    judgement = false;
                    continue;
                }
                break;
            }   
        }
        for (int i = 0; i < arr.length; i++){
            System.out.println(arr[i]);
        }
    }

}

//厉害方法
int[] arr = new int[6];
        for (int i = 0; i < arr.length; i++) {// [0,1) [0,30) [1,31)
            arr[i] = (int) (Math.random() * 30) + 1;
            
                for (int j = 0; j < i; j++) {
                    if (arr[i] == arr[j]) {
                        i--;
                        break;
                    }
                }
            }

        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

练习二

/*
 * 回形数格式方阵的实现
从键盘输入一个整数（1~20） 
则以该数字为矩阵的大小，把1,2,3…n*n 的数字按照顺时针螺旋的形式填入其中。例如： 输入数字2，则程序输出： 1 2 
4 3 
输入数字3，则程序输出： 1 2 3 
8 9 4 
7 6 5 
输入数字4， 则程序输出： 
1   2   3   4 
12  13  14  5 
11  16  15  6 
10   9  8    7

 */
import java.util.Scanner;
public class ArrayExer4 {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int len = scanner.nextInt();
        int[][] arr = new int[len][len];
        int s = len * len;
        int k = 1;
        int i = 0, j = 0;
        
        for(int m = 1;m < s;m++){
            if (k == 1){
                if (j < len && arr[i][j] == 0){
                    arr[i][j++] = m;
                }else{
                    k = 2;
                    i++;
                    j--;
                    m--;
                }
            }else if (k == 2){
                if (i < len && arr[i][j] == 0){
                    arr[i++][j] = m;
                    
                }else{
                    k = 3;
                    i--;
                    j--;
                    m--;
                }
            }else if (k == 3){
                if (j >= 0 && arr[i][j] == 0){
                    arr[i][j--] = m;
                }else{
                    k = 4;
                    i--;
                    j++;
                    m--;
                    
                }
            }else if (k == 4){
                if (i >= 0 && arr[i][j] == 0){
                    arr[i--][j] = m;
                    
                }else{
                    k = 1;
                    i++;
                    j++;
                    m--;
                }
            }
        }
        for (int m = 0; m < arr.length;m++){
            for(int n = 0;n < arr[m].length;n++){
                System.out.print(arr[m][n] + "\t");
            }
            System.out.println();
        }
    }

}

练习三

/*
 * 算法的考查：求数值型数组中元素的最大值、最小值、平均数、总和等
 * 
 * 定义一个int型的一维数组，包含10个元素，分别赋一些随机整数，
 * 然后求出所有元素的最大值，最小值，和值，平均值，并输出出来。   
 * 要求：所有随机数都是两位数。
 * 
 * [10,99]
 * 公式：(int)(Math.random() * (99 - 10 + 1) + 10)
 * random得到double型
 */
public class ArrayTest1 {
    public static void main(String[] args){
        int[] arr = new int[10];
        
        for(int i = 0;i < arr.length;i++){
            arr[i] = (int)(Math.random() * (99 - 10 + 1) + 10);
        }
        //遍历
        for(int i = 0;i <arr.length;i++){
            System.out.println(arr[i]);
        }
        System.out.println();
        //求数组最大值
        //int max = 0;
        int max = arr[0];
        for(int i = 0;i <arr.length;i++){
            if(max < arr[i]){
                max = arr[i];
            }
        }
        System.out.println(max);
        //求数组最小值
        int min =arr[0];
        for(int i = 0;i <arr.length;i++){
            if(min > arr[i]){
                min = arr[i];
            }
        }
        System.out.println(min);
        //求数组总和
        int sum = 0;
        for(int i = 0;i <arr.length;i++){
            sum += arr[i];
        }
        System.out.println(sum);
        //求数组平均数
        int avg = sum / arr.length;
        System.out.println(avg);
    }

}

练习四

/*
 * 使用简单数组
(1)创建一个名为ArrayExer5的类，在main()方法中声明array1和array2两个变量，他们是int[]类型的数组。
(2)使用大括号{}，把array1初始化为8个素数：2,3,5,7,11,13,17,19。
(3)显示array1的内容。
(4)赋值array2变量等于array1，修改array2中的偶索引元素，使其等于索引值(如array[0]=0,array[2]=2)。打印出array1。
 * 
 * 思考：array1和array2是什么关系？array1和array2地址值相同，都指向了堆空间的唯一的一个数组实体。
 * 拓展：修改题目，实现array2对array1数组的复制
 */
public class ArrayExer5 {
    public static void main(String[] args){
        int[] array1,array2;
        array1 = new int[]{2,3,5,7,11,13,17,19};
        //显示array1内容
        for (int i = 0;i < array1.length;i++){
            System.out.print(array1[i] + "\t");
        }
        //赋值array2变量等于array1
        array2 = array1;//仅仅将array1的地址给了array2，但实际上只有一个数组，仅仅是地址值一样
        //只有通过new才会产生新的数组，这里只有一个new
        //此处不能称作数组的复制
        
        //修改array2中的偶索引元素，使其等于索引值(如array[0]=0,array[2]=2)
        for(int i = 0; i < array2.length;i++){
            if(i % 2 ==0){
                array2[i] = i;
            }
        }
        System.out.println();
        //打印出array1
        for(int i = 0;i < array1.length;i++){
            System.out.print(array1[i] + "\t");
        }
    }

}
地址值的变化并非复制

==复制文件与复制快捷方式的区别==

//数组的复制
public class ArrayExer6 {
    public static void main(String[] args){
        int[] array1,array2;
        array1 = new int[]{2,3,5,7,11,13,17,19};
        //显示array1内容
        for (int i = 0;i < array1.length;i++){
            System.out.print(array1[i] + "\t");
        }
        //赋值array2变量等于array1
        array2 = new int[array1.length];
        for(int i = 0;i < array2.length;i++){
            array2[i] = array1[i];
        }
数组的复制操作

练习五

/*
 * 算法的考查：数组的复制、反转、查找(线性查找、二分法查找)
 * 
 * 
 */
public class ArrayTest2 {
    
    public static void main(String[] args) {
        
        String[] arr = new String[]{"JJ","DD","MM","BB","GG","AA"};
        
        
        //数组的复制(区别于数组变量的赋值：arr1 = arr)
        String[] arr1 = new String[arr.length];
        for(int i = 0;i < arr1.length;i++){
            arr1[i] = arr[i];
        }
        //数组的反转
        //法一：注意下标和长度的区别
        for(int i = 0;i < 0.5 * arr.length;i++){
            String transition = arr[i];
            arr[i] = arr[arr.length - i - 1];
            arr[arr.length - i - 1] = transition;
        }
        //法二：
//      for(int i = 0,j = arr.length - 1;i < j;i++,j--){
//          String transition = arr[i];
//          arr[i] = arr[j];
//          arr[j] = transition;
//      }
        for (int i = 0;i < arr.length;i++){
            System.out.print(arr[i] + "\t");
        }
        System.out.println();
        //查找
        //线性查找
        String dest = "BB";
        //equals.:比较字符串内的内容是否相同
        boolean isFlag = true;//标识判断
        for(int i = 0;i < arr.length;i++){
            if(dest.equals(arr[i])){
                System.out.println("找到了指定的元素：位置为：" + i);
                isFlag = false;
                break;
            }   
        }
        if(isFlag){
            System.out.println("很遗憾，未找到");
        }   
        //二分法查找：相对于线性查找，更快速
        //前提：所要查找的数组必须有序
        int[] arr2 = new int[]{-98,-40,-34,-5,3,4,25,34,90};
        int dest1 = -34;
        int head = 0;//初始的索引;
        int end = arr2.length - 1;//初始的末索引
        boolean isFlag1 = true;
        while (head <= end){
            int middle = (head + end)/2;
            if(dest1 == arr2[middle]){
                System.out.println("找到了指定的元素，索引位置为" + middle);
                isFlag1 = false;
                break;
            }else if(arr2[middle] > dest1){
                end = middle - 1;
            }else{
                head = middle + 1;
            }
        }
        if(isFlag1){
            System.out.println("很遗憾，未找到");
        }
    }
}
二分法

排序算法

排序：假设含有n个记录的序列为{R1,R2,...Rn}，其相应的关键字序列为{K1,K2,...Kn}。将这些记录重新排序为{Ri1,Ri2,...<Rin}，使得相应的关键字值满足条件Ki1<=Ki2<=Ki3<=...<=Kin,这样的一种操作称为排序。

  • 通常来说，排序的目的是为了快速查找

  • 衡量排序算法的优劣：

    • 时间复杂度：分析关键字的比较次数和记录的移动次数
    • 空间复杂度：分析排序算法中需要多少辅助内存
    • 稳定性：若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种算法是稳定的。

  • 排序算法分类：内部排序和外部排序

    • 内部排序：整个排序过程中不需要借助于外部存储器(如磁盘等)，所有排序操作都在内存中完成。
    • 外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器(如磁盘)。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。

  • 十大内部排序算法

    • 选择排序
      • 直接选择排序
      • *堆排序 *
    • 交换排序
      • ==冒泡排序==
      • ==快速排序==
    • 插入排序
      • 直接插入排序
      • 折半插入排序
      • Shell排序(希尔排序)
    • 归并排序
    • 桶式排序
    • 基数排序

  • 算法的5大特征

    • 输入(input):有0个或多个输入数据，这些输入数据必须有清楚的描述和定义
    • 输出(Output):至少有1个或多个输出结果，不可以没有输出结果
    • 有穷性(有限性，Finiteness):算法在有限的步骤之后会自动结束而不会无线循环，并且每一个步骤可以在可接受的时间内完成
    • 确定性(明确性，Definiteness):算法的每一步都有确定的含义，不会出现二义性
    • 可行性(有效性，Effectiveness):算法的每一步都是清楚且可行的，能让用户用纸笔计算求出答案

==人们也关注并不要求终止的计算描述，这种描述有时被称为过程(procedure)==

冒泡排序

  • 比较相邻的元素。如果第一个二大（升序），就交换他们两
  • 对每一相邻元素作同样的工作，从开始第到结尾最后。这步做完后，最后的元素会是大数。
  • 针对所有的元素重复以上步骤，除了最后一个。
  • 持续每次对越来少的元素重复上面步骤，直到没有任何一数字需要比较为止。
public class BubbleSortTest {
    public static void main(String[] args) {
        
        int[] arr = new int[]{43,32,76,-98,0,64,33,-21,32,99};
        
        //冒泡排序
        for(int i = 0;i < arr.length - 1;i++){
            
            for(int j = 0;j < arr.length - 1 - i;j++){
                
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                
            }
        for(int i = 0;i < arr.length - 1;i++){
            System.out.print(arr[i] + "\t");
        }
    }
}

快速排序

  • 快速排序通常明显比O(nlogn)的其他算法更快，因此常被采用，快速排序算法采用了分治法的思想

排序思想

  • 从数列中挑出一个元素，称为"基准"(pivot)
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准后面(相同的数可以到任一边)。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区(partition)操作
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序
  • 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代(iteration)中，它至少会把一个元素摆到它最后的位置去
快速排序过程
/**
 * 快速排序
 * 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，
 * 则分别对这两部分继续进行排序，直到整个序列有序。
 */
public class QuickSort {
    private static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    private static void subSort(int[] data, int start, int end) {
        if (start < end) {
            int base = data[start];
            int low = start;
            int high = end + 1;
            while (true) {
                while (low < end && data[++low] - base <= 0)
                    ;
                while (high > start && data[--high] - base >= 0)
                    ;
                if (low < high) {
                    swap(data, low, high);
                } else {
                    break;
                }
            }
            swap(data, start, high);
            
            subSort(data, start, high - 1);//递归调用
            subSort(data, high + 1, end);
        }
    }
    public static void quickSort(int[] data){
        subSort(data,0,data.length-1);
    }
    
    
    public static void main(String[] args) {
        int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
        System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
        quickSort(data);
        System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
    }
}

排序算法的的性能对比

  • 从平均时间而言 ：快速排序最佳。 但在最坏情况下时间性能不如堆排序和归并排序。
  • 从算法简单性看 ：由于直接选择排序、插入和冒泡的算法比较简单，将其认为是简单算法。 对于Shell排序 、堆排序、快速排序和归并排序算法，其算法比较复杂，认为是复杂排序。
  • 从稳定性看：直接插入排序、冒泡排序和归并排序时稳定的；而直接选择排序、快速排序、shell排序和堆排序是不稳定排序。
  • 从待排序的记录数n的大小看 ，n较小时，宜采用简单排序；而 n较大时宜采用改进排序
排序算法的性能

Arrays工具类的使用

  • java.util.Arrays类即为操作数组的工具类，包含用来操作数组(比如排序和搜索)的各种方法。
Arrays工具类常见方法
import java.util.Arrays;
/*
 * java.util.Arrays:操作数组的工具类，里面定义了很多操作数组的方法
 * 
 * 
 */
public class ArraysTest {
    public static void main(String[] args) {
        
        //1.boolean equals(int[] a,int[] b):判断两个数组是否相等。数组要有顺序
        int[] arr1 = new int[]{1,2,3,4};
        int[] arr2 = new int[]{1,3,2,4};
        boolean isEquals = Arrays.equals(arr1, arr2);
        System.out.println(isEquals);
        
        //2.String toString(int[] a):输出数组信息。
        System.out.println(Arrays.toString(arr1));
        
            
        //3.void fill(int[] a,int val):将指定值填充到数组之中。
        Arrays.fill(arr1,10);
        System.out.println(Arrays.toString(arr1));
        

        //4.void sort(int[] a):对数组进行排序。
        Arrays.sort(arr2);
        System.out.println(Arrays.toString(arr2));
        
        //5.int binarySearch(int[] a,int key)
        int[] arr3 = new int[]{-98,-34,2,34,54,66,79,105,210,333};
        int index = Arrays.binarySearch(arr3, 210);
        if(index >= 0){
            System.out.println(index);
        }else{
            System.out.println("未找到");
        }
        
        
    }
}

数组使用中的常见异常

/*
 * 数组中的常见异常：
 * 1. 数组角标越界的异常：ArrayIndexOutOfBoundsExcetion
 * 
 * 2. 空指针异常：NullPointerException
 * 
 */
public class ArrayException {
    public static void main(String[] args) {
        
        //1. 数组角标越界的异常：ArrayIndexOutOfBoundsExcetion,不在指定的范围内的情况
        int[] arr = new int[]{1,2,3,4,5};
        
//      for(int i = 0;i <= arr.length;i++){
//          System.out.println(arr[i]);
//      }此处出现了角标5
        
//      System.out.println(arr[-2]);
        
//      System.out.println("hello");
        
        //2.2. 空指针异常：NullPointerException
        //情况一：
//      int[] arr1 = new int[]{1,2,3};
//      arr1 = null;
//      System.out.println(arr1[0]);
        
        //情况二：
//      int[][] arr2 = new int[4][];
//      System.out.println(arr2[0][0]);
        
        //情况三：
        String[] arr3 = new String[]{"AA","BB","CC"};
        arr3[0] = null;
        System.out.println(arr3[0].toString());
    }
}

数组重点

  • 一维数组使用！！！
  • 二维数组使用！！！
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 219,539评论 6赞 508
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,594评论 3赞 396
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 165,871评论 0赞 356
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,963评论 1赞 295
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,984评论 6赞 393
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,763评论 1赞 307
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,468评论 3赞 420
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,357评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,850评论 1赞 317
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,002评论 3赞 338
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,144评论 1赞 351
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,823评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,483评论 3赞 331
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,026评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,150评论 1赞 272
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,415评论 3赞 373
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 45,092评论 2赞 355