数组
- 数组是相同类型数据的有序集合
- 每一个数据称作一个数据元素，每个数组元素可以通过一个下标来访问
- 获取数组长度：array.length
数组的使用
- 声明数组
dataType[] arrayName;
- 初始化数组
- 在声明时初始化
int[] numbers = new int[5]; // 创建一个长度为5的整型数组
- 在声明之后初始化
int[] numbers;
numbers = new int[5]; // 创建一个长度为5的整型数组
- 初始化数组并赋初值
int[] numbers = {1, 2, 3, 4, 5};
- 访问数组元素
arrayName[i];
- 修改数组元素
arrayName[i] = 10;
- 遍历数组
- 使用 for 循环
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
- 使用增强的 for 循环（foreach）
for (int element : array) {
System.out.println(element);
}
- 数组的常见操作
- 获取数组长度
x = array.length;
- 查找元素
int[] numbers = {1, 2, 3, 4, 5};
int target = 3;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == target) {
System.out.println("找到了目标元素，索引为：" + i);
break;
}
}
- 排序数组
使用 Arrays.sort() 方法对数组进行排序。
import java.util.Arrays;
int[] numbers = {5, 3, 1, 4, 2};
Arrays.sort(numbers);
for (int element : numbers) {
System.out.println(element);
}
- 复制数组
使用 System.arraycopy() 或 Arrays.copyOf() 方法复制数组。
int[] sourceArray = {1, 2, 3, 4, 5};
int[] destinationArray = new int[sourceArray.length];
System.arraycopy(sourceArray, 0, destinationArray, 0, sourceArray.length);
int[] sourceArray = {1, 2, 3, 4, 5};
int[] destinationArray = Arrays.copyOf(sourceArray, sourceArray.length);
内存分析
- 声明数组：堆中不分配空间，栈中开辟空间压入变量名
- 创建数组：在堆中分配空间，栈与堆建立对应关系
- 给数组赋值：在堆中对应的空间中存入值
- 三种初始化方式：
- 静态初始化：创建的同时赋值
- 动态初始化：创建后赋值（包含默认赋值）
- 默认初始化
数组是引用类型，他的元素相当于类的示例变量，因此数组一经分配空间，其中的每个元素也被按照示例变量同样的方式被隐式初始化
数组的长度是确定、不可变的
二维数组及多维数组
- 二维数组实际是一维数组的嵌套
- 多维数组类似
Arrays类
- Java的标准类库java.util.Arrays
- 打印数组元素使用Arrays.toString()方法
- 对于二维数组，可以先使用循环遍历每一行，然后对每一行使用Arrays.toString()方法
冒泡排序
- 共有八大排序算法，冒泡排序（Bubble Sort）是最为出名的一种排序算法
public class BubbleSortExample {
public static void main(String[] args) {
int[] array = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(array);
System.out.println("Sorted array : ");
for (int value : array) {
System.out.print(value + " ");
}
}
static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
// "swapped" 用于优化冒泡排序，如果一轮下来没有发生交换，则说明数组已经是有序的了
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果这一轮没有发生任何交换，那么数组已经排序好了，可以提前结束
if (!swapped)
break;
}
}
}
稀疏数组
- 稀疏数组是一种处理稀疏矩阵的数据结构。在计算机科学中，稀疏矩阵是指绝大多数元素都是零的矩阵。直接存储这样的矩阵会造成空间的极大浪费，因为大部分存储空间都用来存储零值。因此，我们通常只存储非零元素及其位置信息。
- 稀疏数组可以通过一个二维数组来实现，其中每个元素表示原始矩阵中的一个非零元素。每个这样的元素通常包含三个信息：行索引、列索引以及该位置上的实际值。
假设有一个4x4的矩阵，它是稀疏矩阵：
0 0 3 0
9 0 0 0
0 0 0 5
0 7 0 0
通常在稀疏数组的第一行会保存矩阵的行数、列数和非零元素的数量。对于以上稀疏矩阵，稀疏数组可以表示为：
行 列 值
4 4 4 // 行数、列数、非零元素数量
0 2 3
1 0 9
2 3 5
3 1 7
示例代码：将一个稀疏矩阵转换成稀疏数组，并且如何从稀疏数组还原回稀疏矩阵：
- 第一种方式
public class SparseArrayExample {
public static void main(String[] args) {
// 原始稀疏矩阵
int[][] originalMatrix = {
{0, 0, 3, 0},
{9, 0, 0, 0},
{0, 0, 0, 5},
{0, 7, 0, 0}
};
// 转换为稀疏数组
int[][] sparseArray = convertToSparse(originalMatrix);
// 输出稀疏数组
printSparseArray(sparseArray);
// 从稀疏数组还原为稀疏矩阵
int[][] recoveredMatrix = recoverFromSparse(sparseArray, originalMatrix.length);
// 输出恢复后的矩阵
printMatrix(recoveredMatrix);
}
private static int[][] convertToSparse(int[][] matrix) {
int nonZeroCount = countNonZero(matrix);
int[][] sparse = new int[nonZeroCount + 1][3];
sparse[0][0] = matrix.length;
sparse[0][1] = matrix[0].length;
sparse[0][2] = nonZeroCount;
int m = 1;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] != 0) {
sparse[m][0] = i;
sparse[m][1] = j;
sparse[m++][2] = matrix[i][j];
}
}
}
return sparse;
}
private static int countNonZero(int[][] matrix) {
int count = 0;
for (int[] row : matrix) {
for (int element : row) {
if (element != 0) count++;
}
}
return count;
}
private static void printSparseArray(int[][] sparseArray) {
for (int[] row : sparseArray) {
System.out.println(row[0] + " " + row[1] + " " + row[2]);
}
}
private static int[][] recoverFromSparse(int[][] sparse, int size) {
int[][] recovered = new int[size][sparse[0][1]];
for (int i = 1; i < sparse.length; i++) {
recovered[sparse[i][0]][sparse[i][1]] = sparse[i][2];
}
return recovered;
}
private static void printMatrix(int[][] matrix) {
for (int[] row : matrix) {
for (int element : row) {
System.out.print(element + " ");
}
System.out.println();
}
}
}
- 第二种方式
public class SparseArrayExample {
public static void main(String[] args) {
// 原始稀疏矩阵
int[][] originalMatrix = {
{0, 0, 3, 0},
{9, 0, 0, 0},
{0, 0, 0, 5},
{0, 7, 0, 0}
};
// 转换为稀疏数组
int[][] sparseArray = convertToSparse(originalMatrix);
// 输出稀疏数组
printSparseArray(sparseArray);
// 从稀疏数组还原为稀疏矩阵
int[][] recoveredMatrix = recoverFromSparse(sparseArray);
// 输出恢复后的矩阵
printMatrix(recoveredMatrix);
}
private static int[][] convertToSparse(int[][] matrix) {
int nonZeroCount = countNonZero(matrix);
int[][] sparse = new int[nonZeroCount + 1][3];
sparse[0][0] = matrix.length;
sparse[0][1] = matrix[0].length;
sparse[0][2] = nonZeroCount;
int m = 1;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] != 0) {
sparse[m][0] = i;
sparse[m][1] = j;
sparse[m++][2] = matrix[i][j];
}
}
}
return sparse;
}
private static int countNonZero(int[][] matrix) {
int count = 0;
for (int[] row : matrix) {
for (int element : row) {
if (element != 0) count++;
}
}
return count;
}
private static void printSparseArray(int[][] sparseArray) {
for (int[] row : sparseArray) {
System.out.println(row[0] + " " + row[1] + " " + row[2]);
}
}
private static int[][] recoverFromSparse(int[][] sparse) {
// 获取原始矩阵的行数和列数
int numRows = sparse[0][0];
int numCols = sparse[0][1];
// 初始化新矩阵
int[][] recovered = new int[numRows][numCols];
// 填充新矩阵
for (int i = 1; i < sparse.length; i++) {
int row = sparse[i][0];
int col = sparse[i][1];
int value = sparse[i][2];
recovered[row][col] = value;
}
return recovered;
}
private static void printMatrix(int[][] matrix) {
for (int[] row : matrix) {
for (int element : row) {
System.out.print(element + " ");
}
System.out.println();
}
}
}
- 两种不同方式还原稀疏数组的比较
- 在这两种方式中，主要的区别在于如何确定恢复后的矩阵的大小。具体来说：
- 第一种方式，除了稀疏数组外，还需要额外传递一个参数来指定恢复后的矩阵大小。这通常是为了确保在某些情况下能够正确地创建目标矩阵，特别是当稀疏数组的第一行数据可能缺失或不可靠时。
- 第二种方式，恢复矩阵的方法直接从稀疏数组的第一行读取原始矩阵的行数和列数信息。这是因为在转换为稀疏数组时，通常会将这些信息存储在稀疏数组的第一行，以便于后续的恢复操作。
- 在实际应用中，通常推荐使用仅传入稀疏数组的方式来实现稀疏矩阵的恢复，因为这种方法更符合稀疏数组的设计初衷，即在一个紧凑的数据结构中包含所有必要的信息。此外，这种方式也使得代码更加简洁易懂。
然而，在某些特殊情况下，如果存在稀疏数组可能被篡改或者数据来源不可信的情况，那么显式地传递矩阵大小可能是更好的选择，以确保即使稀疏数组的第一行信息丢失也能正确恢复矩阵。
关于变量的声明和创建
在Java中，声明变量和创建变量实际上是两个不同的步骤，它们分别涉及内存分配和类型安全。
- 声明变量
声明变量是指告诉编译器你打算使用一个特定类型的变量。声明仅涉及到变量的类型和名字，而不涉及内存分配。- 创建变量（初始化）
创建变量或初始化是指给变量分配内存，并赋予初始值。这是实际为变量分配内存空间的过程。
为什么分开
- 内存管理
- 延迟初始化：有时候，我们可能并不需要立即初始化一个变量，而是稍后才会给它赋值。这时，我们可以先声明变量，等到需要的时候再初始化。
- 内存优化：通过延迟初始化，可以避免不必要的内存分配，特别是在处理大型对象时，这样可以节省内存资源。
- 类型安全
- 编译时检查：Java是一门静态类型语言，声明变量时就已经确定了它的类型。这允许编译器在编译阶段进行类型检查，确保变量的使用符合其类型定义。
- 强制初始化：在某些情况下，如局部变量在使用之前必须初始化。这有助于防止未初始化变量带来的潜在问题。
声明和创建（初始化）分开可以使代码更清晰、更具灵活性，并且有助于提高程序的健壮性和效率。
关于类、实例、对象和成员
实例和对象是完全一样的吗
在面向对象编程的语言中，“实例”和“对象”通常是可以互换使用的，但是从概念上讲，“实例”更强调的是类的一个具体实现或存在形式，而“对象”则更多地指代现实世界中的实体映射到程序中的抽象。
-
对象（Object）
- 对象是指现实世界中的事物或概念的抽象表示，在程序中通常由类来定义其属性和行为。
- 在Java中，所有的东西都是对象，因为所有类的实例都是java.lang.Object类的子类。
- 对象是由类创建出来的具体实例。
-
实例（Instance）
- 实例强调的是类的一个特定示例或实现。
- 当我们说某个东西是类的一个实例时，我们指的是基于该类创建的一个具体对象。
- 每个实例都有自己独立的一套类中定义的属性值，但是它们共享同一套行为（方法）。
-
实例和对象的关系
- 每当使用new关键字创建一个类的新对象时，就创建了一个类的实例。
- 在Java中，当我们说“创建一个对象”，实际上是在说“创建一个类的实例”。
- 总的来说，虽然我们经常将“实例”和“对象”视为同义词使用，但从理论上讲，“实例”更侧重于强调它是类的一个具体实现，而“对象”则更多地指向那个抽象的概念实体。
- 在实际编码过程中，这两个术语通常是可以互换的。
类、实例（对象）和成员的关系
在Java中，类、实例（对象）、以及成员之间的关系是面向对象编程的核心概念。
- 类（Class）
类是一种模板或蓝图，定义了一组具有相似属性和行为的对象。它本身不是具体存在的实体。类定义了对象的状态（属性或字段）和行为（方法）。
- 实例（Instance）/ 对象（Object）
实例是由类创建的具体对象。每个实例都有自己的状态，但共享相同的类定义的行为。对象就是类的一个实例。
- 成员（Members）
成员指的是类中的属性（字段）和方法。成员可以分为两种类型：
- 字段（Fields）：字段是类中定义的变量，表示对象的状态。
- 方法（Methods）：方法是类中定义的函数，表示对象的行为。