1, Overview of arrays

1. Understanding of arrays:

An array is a collection of several data of the same type arranged in a certain order, named with a name, and managed uniformly by numbering.

2. Array related concepts:

Array name element subscript, subscript and index length of array: number of elements

3. Characteristics of array:

• Arrays are ordered
• Array is a variable of reference data type. The element of an array can be either a basic data type or a reference data type
• Creating an array object opens up a whole contiguous space in memory
• Once the length of the array is determined, it cannot be modified.

4. Array classification:

① According to dimension: one-dimensional array, two-dimensional array...

② According to the type of array elements: array of basic data type elements and array of reference data type elements

5. Data structure:

• Logical relationship between data and data: set (weak relationship), one-to-one (elements in the array), one to many (binary tree), many to many (Social Network)
• Data storage structure: linear table: sequential table (such as array), linked list, stack, queue tree structure: binary tree graphic structure:

2, One dimensional array

1. Declaration and initialization of one-dimensional array

The right way:

int num;//statement
num = 10;//initialization
int id = 1001;//Declaration + initialization		
int[] ids;//statement
//1.1 static initialization: the initialization of array and the assignment of array elements are carried out at the same time
ids = new int[]{1001,1002,1003,1004};
//1.2 dynamic initialization: the initialization of array and the assignment of array elements are carried out separately
String[] names = new String[5];
int[] arr4 = {1,2,3,4,5};//Type inference

Wrong way:

//int[] arr1 = new int[];
//int[5] arr2 = new int[5];
//int[] arr3 = new int[3]{1,2,3};

2. Reference of one-dimensional array elements:

Called by means of corner markers.

//The subscript (or index) of the array starts from 0 and ends with the length of the array - 1.
names[0] = "Wang Ming";
names[1] = "Wang He";
names[2] = "placed under house arrest";
names[3] = "Sun Julong";
names[4] = "Wang Hongzhi";//charAt(0)

3. Array properties:

Attribute of array: length

System.out.println(names.length);//5
System.out.println(ids.length);

Description: once the array is initialized, its length is determined. Once the array length of arr.length is determined, it cannot be modified.

4. Traversal of one-dimensional array

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

5. Default initialization value of one-dimensional array element

• Array element is integer: 0
• Array elements are floating point: 0.0
• Array elements are char type: 0 or '\ u0000', not '0'
• Array elements are boolean: false
• Array element is a reference data type: null

6. Memory structure of one-dimensional array

3, Two dimensional array

1. How to understand two-dimensional array?

An array is an element that refers to an array of data types. It can also be an element that refers to a one-dimensional array a of data types. If it is also a one-dimensional array type, then this array A is called a two-dimensional array.

2. Declaration and initialization of two-dimensional array

The right way:

int[] arr = new int[]{1,2,3};//One dimensional array
//initiate static
int[][] arr1 = new int[][]{{1,2,3},{4,5},{6,7,8}};
//Dynamic initialization 1
String[][] arr2 = new String[3][2];
//Dynamic initialization 2
String[][] arr3 = new String[3][];
//It is also the correct way to write:
int[] arr4[] = new int[][]{{1,2,3},{4,5,9,10},{6,7,8}};
int[] arr5[] = {{1,2,3},{4,5},{6,7,8}};//Type inference

Wrong way:

//String[][] arr4 = new String[][4];
//String[4][3] arr5 = new String[][];
//int[][] arr6 = new int[4][3]{{1,2,3},{4,5},{6,7,8}};

3. How to call two-dimensional array elements:

System.out.println(arr1[0][1]);//2
System.out.println(arr2[1][1]);//null
		
arr3[1] = new String[4];
System.out.println(arr3[1][0]);
System.out.println(arr3[0]);//

4. Properties of two-dimensional array:

System.out.println(arr4.length);//3
System.out.println(arr4[0].length);//3
System.out.println(arr4[1].length);//4

5. Traverse two-dimensional array elements

for(int i = 0;i < arr4.length;i++){
			
	for(int j = 0;j < arr4[i].length;j++){
		System.out.print(arr4[i][j] + "  ");
	}
	System.out.println();
}

6. Default initialization value of two-dimensional array elements

 * 	Regulation: the two-dimensional array is divided into the elements of the outer array and the elements of the inner array
 * 		int[][] arr = new int[4][3];
 * 		Outer elements: arr[0],arr[1]etc.
 * 		Inner element: arr[0][0],arr[1][2]etc.
 * 
 *   ⑤ Default initialization value of array elements 
 *   For initialization method 1: for example: int[][] arr = new int[4][3];
 *      The initialization value of the outer element is: address value
 *      The initialization value of the inner element is: the same as that of the one-dimensional array
 *      
 *   For initialization mode 2: for example: int[][] arr = new int[4][];
 *   	The initialization value of the outer element is: null
 *      The initialization value of the inner element is: it cannot be called, otherwise an error will be reported.

7. Memory structure of two-dimensional array

4, Common algorithms for arrays

1. Creation of array and element assignment:

Yang Hui triangle (two-dimensional array), loop number (two-dimensional array), 6 numbers, randomly generated between 1-30 and not repeated.

Yanghui triangle

// 1. Create a new binary array and initialize dynamically
int[][] yangHui = new int[10][];
// 2. Assign value to two-dimensional array
for (int i = 0; i < yangHui.length; i++) {
    yangHui[i] = new int[i + 1];
    // 2.1 assignment of first and last elements
    yangHui[i][0] = yangHui[i][i] = 1;
    // 2.2 assign values to other elements
    for (int j = 1; j < yangHui[i].length - 1; j++) {//
        yangHui[i][j] = yangHui[i - 1][j - 1] + yangHui[i - 1][j];
    }

}
// 3. Print out two-dimensional array
for (int i = 0; i < yangHui.length; i++) {
    for (int j = 1; j < yangHui[i].length; j++) {// There is no element at position 0
        System.out.print(yangHui[i][j] + " ");
    }
    System.out.println();
}

2. For numeric arrays:

Maximum, minimum, sum, average, etc

// 1. Find the maximum value in the array
int maxArr = arr[0];
for (int i = 0; i < arr.length; i++) {
    if (maxArr < arr[i]) {
        maxArr = arr[i];
    }
}
System.out.println("The maximum value in the array is:" + maxArr);

// 2. Find the smallest value in the array

int minArr = arr[0];
for (int i = 0; i < arr.length; i++) {
    if (minArr > arr[i]) {
        minArr = arr[i];
    }
}
System.out.println("The minimum value in the array is:" + minArr);

// 3. Find the average in the array
int num = 0;
for (int i = 0; i < arr.length; i++) {
    num += arr[i];
}
System.out.println("The average number of arrays is:" + (num / arr.length));

// 4. Sum
int num1 = 0;
for (int i = 0; i < arr.length; i++) {
    num1 += arr[i];
}
System.out.println("The sum of the array is:" + num1);

3. Assignment and copy of array

// 1. Assignment of array
String[] str1 = new String[5];
str1 = str;
str1[2] = "AA";
for (int i = 0; i < str1.length; i++) {
    System.out.print(str[i] + " ");
}
System.out.println();

3.1 assignment

How to understand: how to understand: assign the address value of the array saved by array1 to array2, so that array1 and array2 point to the same array entity in the heap space.

3.2 reproduction:

// 1.1 copy of array
for (int i = 0; i < str1.length; i++) {
    str1[i] = str[i];
    System.out.print(str1[i] + " ");
}

How to understand: we use the new method to open up a new array space for array2 in the heap space. Assign the element values in array1 array to array2 array one by one.

4. Inversion of array elements:

//Method 1:
for(int i = 0;i < arr.length / 2;i++){
    String temp = arr[i];
    arr[i] = arr[arr.length - i -1];
    arr[arr.length - i -1] = temp;
}

//Method 2:
for(int i = 0,j = arr.length - 1;i < j;i++,j--){
    String temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

5. Search for specified elements in the array: search, retrieve

5.1 linear search:

Implementation idea: compare and search the data one by one through traversal. Applicability: universal adaptability

5.2 dichotomy search:

Implementation idea: compare the intermediate value every time and search in half. Applicability: (premise: the array must be ordered)

6 . Sorting algorithm of array

Top ten sorting algorithms

• Select sort:
  Direct selection sorting and heap sorting
• Swap sort:
  Bubble sort, quick sort
• Insert sort:
  Direct insert sort, half insert sort, Hill sort
• Merge sort
• Bucket sorting
• Cardinality sort

understand:

1) Measure the advantages and disadvantages of sorting algorithm:

Time complexity, space complexity, stability

2) Sorting classification: internal sorting and external sorting (with the help of disk)

3) Time complexity of different sorting algorithms

Implementation of bubble sorting:

		int[] arr = new int[] { 21, 43, 64, 76, 878, 432, 21 };
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; 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; i++) {
            System.out.print(arr[i] + " ");
        }

5, Use of Arrays tool class

1. Understand:

① Defined in Java Util package. ② Arrays: provides many ways to manipulate arrays.

2. Use:

int arr1[] = new int[] { 21, 43, 542, 432, 4, 2, 5, 1 };
int arr2[] = new int[] { 32, 43, 4, 1, 4, 76, 54, 68, 4 };

// 1.Arrays.equals(arr1, arr2): judge whether the arrays are equal
System.out.println(Arrays.equals(arr1, arr2));
// 2.Arrays.toString(arr1): output array information
System.out.println(Arrays.toString(arr1));

// 3.Arrays.fill(arr1, 2): fills the array with the specified value
Arrays.fill(arr1, 2);
System.out.println(Arrays.toString(arr1));
// 4.Arrays.sort(arr2): sort the array
Arrays.sort(arr2);
System.out.println(Arrays.toString(arr2));
// 5.Arrays. Binary search (arr2, 1): the array sorted by the heap retrieves the specified value by dichotomy
int index = Arrays.binarySearch(arr2, 1);
System.out.println(index);

6, Common exceptions to arrays

1. Array subscript out of bounds exception:

ArrayIndexOutOfBoundsException

int[] arr = new int[]{1,2,3,4,5};

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

System.out.println(arr[-2]);

System.out.println("hello");

2. Null pointer exception:

NullPointerException

//Case 1:
int[] arr1 = new int[]{1,2,3};
arr1 = null;
System.out.println(arr1[0]);

//Case 2:
int[][] arr2 = new int[4][];
System.out.println(arr2[0][0]);

//situation:
String[] arr3 = new String[]{"AA","BB","CC"};
arr3[0] = null;
System.out.println(arr3[0].toString());

Tip: once the program has an exception and is not handled, the execution will be terminated.