《Java小子怒闯数据结构九重天》第一重天——数组

2年前 (2022) 程序员胖胖胖虎阿

314 0 0

本专栏文章主要用于帮助Java使用者快速上手数据结构，刷算法题！

前言

自古以来数据结构界就分为九重天，据说冲破这九重天之后就可以去进攻算法界最终修炼最后成佬，受万人敬仰。

但是这谈何容易，因为每一重天都有神兽把守，想要冲破每一重天都必须收服守护的神兽才行。

守护九重天的神兽分别是：数组、字符串、栈、队列、链表、树、散列表、堆、图。可见他们的战斗力也是逐层增强的。想只凭靠自身的能力拿下他们谈何容易。

不过大家不必惊慌，我这里有一本上古秘籍《Java小子怒闯数据结构九重天》，里面有每一重天神兽的攻略。只要修炼者仔细钻研里面的每一篇，对九重天了如指掌之后，冲破这九重天也是易如反掌的。

今天为大家带来第一重天的攻略！
《Java小子怒闯数据结构九重天》第一重天——数组

1.🌀数组基础知识

数组：数组是可以在内存中连续存储多个相同类型的数据元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。

1.1 数组中需要注意的点：

数组的本质是什么呢？数组就是一片地址连续且空间大小一致的存储空间(但是每个空间存的还是其他数据的地址)
为什么空间大小是相等的呢？就是为了方便统一维护我们的数据，必须得保证数据之间的类型是一样的。（多个同类型的变量空间连在一起组成的结构叫数组）
数组存在于堆内存中，但凡在堆中存储的数据都称之为对象，但凡在堆内存中创建的对象都会有默认初始值
（1）整数类型数组默认值均为0
（2）浮点类型数组默认值均为0.0
（3）布尔类型数组默认值均为false
数组变量存的就是数组在堆内存中首元素的地址
数组一旦定义下来，其长度不可改变；
创建数组时必须明确规定大小或内容
二维数组我们也称之为矩阵，即：数组中的每一个元素为一个矩阵。如矩阵a：a[3][3]={{1,2,2}{5,5,9}{8,9,7}}

2.🌀初始化数组

一般来说Java初始化数组为以下格式，声明数组的同时开辟数组空间。

数组类型[] 数组名 = new 数据类型[数组长度];

这里的两个类型都是相同的只不过叫法不一样而已，要注意的是类型可以是8种基本的数据类型，也可以是引用数据类型。

这里的引用类型也可以是自已创建类型，假如你创建了一个关于图书的Book类，那么你也可以为Book类创建一个数组，如：

Book[] books = new Book[3];

这里就是创建了三本书的一个数组。

除了以上方式创建数组之外我们还会把声明数组与开辟空间分开来进行初始化数组。如下：

//声明数组变量
String[] arr;
int arr1[];
//数组对象实例化长度为3(开辟数组空间)
arr1 = new int[3];
arr = new String[3];

或者我们在创建数组的时候直接给数组进行赋值。这样的话并不会直接声明数组的长度。如下：

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

3.🌀数组常用API

API（Application Programming Interface,应用程序编程接口）是一些预先定义的函数，目的是提供应用程序与开发人员基于某软件或硬件得以访问一组例程的能力，而又无需访问源码，或理解内部工作机制的细节。

在Java中有许多关于数组的API，这些API也会简化一些我们涉及到数组的操作。

而想要收服数组，那么这些API你一定也要熟记于心。

首先关于数组的方法都在java.util.Arrays;这个包下，我们在使用之前也是需要先导入这个包才行。如下：

import java.util.Arrays;

常用数组的一些api或用法如下：

3.1 使用length方法求数组长度

int len = array.length;

3.2 使用for循环遍历打印数组

//方法一：使用普通for循环遍历数组
for(int i = 0; i < array.length; i ++) {
     System.out.println(array[i]);
}
//方法二：使用增强for循环遍历数组
for(int num : array) {
     System.out.println(num);
}

3.3 使用toString()方法将int类型数组转成字符串string类型数组

String arrStrings = Arrays.toString(array);

3.4 使用fill()方法填充数组

//将数组array全部用10填充
Arrays.fill(array, 10);

3.5 使用sort()方法对数组从小到大进行排序；

//方法1:sort(int[] a)   放入数组名字
Arrays.sort(array);
//方法2:sort(a, fromIndex, toIndex)  从第几个到第几个之间的进行排序
Arrays.sort(array, 1 , 4);

3.6 使用copyof()方法复制数组

//方法 1
int[] arr6 = {3, 7, 2, 1};
//指定新数组的长度
int[] arr7 = Arrays.copyOf(arr6, 10);  
//方法 2
//只复制从索引[1]到索引[3]之间的元素（不包括索引[3]的元素）     
int[] arr8 = Arrays.copyOfRange(arr6, 1, 3);

3.7 使用asList()方法将数组转成List集合类型

String[] array = {"1", "2", "3"};
List<String> list = Arrays.asList(array);

3.8 将数组转成set集合

String[] array = new String[]{"1", "2", "3"};
Set<Integer> set = new HashSet(Arrays.asList(array));

4.🌀数组进阶练习

Leetcode 217. 存在重复元素
《Java小子怒闯数据结构九重天》第一重天——数组
解法一：排序法
最容易想到的就是排序了，先对数组元素进行排序，在排序之后相同的元素就会相邻了，我们在遍历数组如果相邻的元素相等，那么说明存在重复元素了。

代码实现：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for(int i = 1; i < nums.length; i ++) {
            if(nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
}

输出结果：
《Java小子怒闯数据结构九重天》第一重天——数组
通过了但是时间复杂度太高。

解法二：利用哈希表的去重特性
创建一个哈希表，然后从左往右遍历数组将数组中的元素加入哈希表。检测哈希表中是否已存在当前字符，若存在，直接返回结果，若不存在，将当前字符加入哈希表，供后续判断使用即可。

代码实现：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet();
        for(int i : nums) {
            if(!set.add(i)) {
                return true;
            }
        }
        return false;
    }
}