Java 数据结构与算法系列精讲之数组

数组的定义和基本操作

数组是一种线性数据结构，它由一系列相同类型的元素组成，这些元素在内存中连续存储。

定义

在Java中定义数组需要指定数据类型和数组长度，例如：

int[] arr = new int[10]; // 定义一个长度为10的整型数组

基本操作

数组的基本操作包括了以下几个方面：

• 初始化：默认初始化为类型的默认值；或者通过指定初始值对数组进行初始化。
• 访问元素：通过下标可以访问数组中的元素，下标从0开始，最大下标为数组长度减1。
• 修改元素：通过下标可以修改数组中的元素。
• 遍历数组：通过循环结构可以遍历数组中的所有元素。

下面是一个遍历和修改数组元素的示例代码：

for (int i = 0; i < arr.length; i++) {
  arr[i] = i * i; // 修改元素
  System.out.println(arr[i]); // 遍历并访问元素
}

数组的实现和常见算法

数组的实现

在Java中，数组的实现采用了连续存储的方式，因此它可以随机访问任何一个元素，时间复杂度为O(1)。

常见算法

线性查找

线性查找是一种简单的查找算法，它从头到尾遍历数组，逐个比对查找元素和数组中的元素，找到则返回元素下标，没有则返回-1。

下面是线性查找的示例代码：

public static int linearSearch(int[] arr, int target) {
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
      return i; // 找到则返回下标
    }
  }
  return -1; // 没有找到则返回-1
}

二分查找

二分查找（折半查找）是一种高效的查找算法，它要求数据必须是有序的，每次将查找区间折半，缩小查找范围，最终找到目标元素或确定不存在。

下面是二分查找的示例代码：

public static int binarySearch(int[] arr, int target) {
  int left = 0;
  int right = arr.length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
      return mid; // 找到目标元素
    } else if (arr[mid] < target) {
      left = mid + 1; // 在右侧查找
    } else {
      right = mid - 1; // 在左侧查找
    }
  }
  return -1; // 没有找到目标元素
}

总结

数组是一种常见的数据结构，它能够随机访问元素，因此可以实现各种常见的算法，如线性查找和二分查找等。在实际开发中，需要熟练掌握数组的定义、基本操作和常见算法，才能更好地解决问题。

阅读剩余 47%