为什么我改看颜群了？原因有这么几点：
- 我现在需要的是快速整理知识体系而非基础入门。
- 小甲鱼课程是C语言实现，而我更擅长Python与Java，且目前以Java为主，所以找一个Java实现的数据结构更合适一些。
- 课时更短。
1. 创建数组
数组是线性结构。创建数组有如下两个方法：
// 方法一：
int[] arr1 = new int[n]; // 一个n长度的元素
// 方法二：给数组添加元素
int[] arr2 = new int[]{ 7, 8, 9 };
2. 为数组添加元素
以添加一个元素为例，步骤如下：
- 创建一个新数组，长度为原数组+1；
- 新数组对位赋值，即原数组什么位置什么数，新数组对位照搬赋值；
- 新数组最后一位赋添加的元素；
- 用新数组替换原数组；
示例代码：
public class Main{
public static void main(String[] args){
int[] arr = new int[]{7, 8, 9};
int[] arr0 = new int[arr.length + 1];
for(int i = 0; i < arr.length; i++){
arr0[i] = arr[i];
}
// 添加元素10
arr0[arr.length] = 10;
// 替换
arr = arr0;
}
}
3. 数组中删除一个元素
步骤如下：
- 创建一个新数组，长度为原数组-1；
- 确定要删除的是第n位。n前面的位新数组与旧数组对位赋值；n后面的移位赋值，即newArr[i] = arr[i + 1]；
- 新数组替换原数组。
示例代码：
public class Main{
public static void main(String[] args){
int[] arr = new int[]{5, 6, 6, 7, 8};
int[] newArr = new int[arr.length - 1];
for (int i = 0; i < (arr.length - 1); i++){
// 删除第2位（索引从0开始）
if (i < 2)
newArr[i] = arr[i];
else
newArr[i] = arr[i + 1];
}
arr = newArr; // 替换
}
}
4. 自建可变数组类型
直接上代码。其他看注释。
package com.Arr;
import java.util.Arrays;
public class MyArray {
private int[] elements; // 用于存储数据的数组
public MyArray(){
elements = new int[0];
} // 创建一个空数组
/**
* Initialise a non-empty array.
* @param n the number of the array
*/
public MyArray(int n){ elements = new int[n]; }
/**
* Get the size of the array.
* @return the length of the array
* */
public int size(){ return elements.length; }
/**
* Add an element to the end of the array.
* @param n the element to be added
* */
public void add(int n){
int[] newArr = new int[elements.length + 1];
for(int i = 0; i < elements.length; i++){
newArr[i] = elements[i];
}
newArr[elements.length] = n;
elements = newArr;
}
/**
* Show the array.
* */
public void show(){ System.out.println(Arrays.toString(elements)); }
/**
* Delete the pointed element.
* @param i the index of the element
* */
public void delete(int i){
if (i < 0 || i > elements.length - 1){ throw new RuntimeException("WRONG!");}
int[] newArr = new int[elements.length - 1];
for(int j = 0; j < newArr.length; j++){
if (j < i){
newArr[j] = elements[j];
}else{
newArr[j] = elements[j + 1];
}
}
elements = newArr;
}
/**
* Get the pointed element.
* @param i the index
* @return the indexed element
* */
public int get(int i){ return elements[i]; }
/**
* Insert an element to the pointed position.
* @param i the position
* @param num the number to be inserted
* */
public void insert(int i, int num){
if (i < 0 || i > elements.length){ // Java中throw的用法
throw new RuntimeException("WRONG!!");
}
int[] newArr = new int[elements.length + 1];
newArr[i] = num;
for(int j = 0; j < (elements.length + 1); j++){
if (j < i){
newArr[j] = elements[j];
}else if(j > i){
newArr[j] = elements[j - 1];
}
}
elements = newArr;
}
}
5. 线性查找
这其实是一个暴力破解法。总体思想是：将目标元素与数组中的元素一个一个比对，找到第一个就返回索引值，没找到就返回-1。比较简单，所以上示例代码：
public class Main {
public static void main(String[] args){
int[] arr = new int[]{3, 4, 5, 6, 7, 8, 9, 10};
int target = 8; // 目标元素
int index = -1; // 默认赋值为-1
for(int i = 0; i < arr.length; i++){
if (arr[i] == target){
index = i; // 如果发现数组中某个元素与target相等，那么就将index改为i值
break; // 跳出循环
} // 如果没有的话，循环一圈之后就什么也没发生
}
System.out.println("index = " + index);
}
}
6. 二分查找
在一个有序数组中（假设从小到大），如果我们要查找target在数组中的哪个位置，那么我们先找到数组中间的那个元素m。如果target > m，向右查；如果target < m，向左查；最幸运的可能是target = m，那还要什么自行车啊（笑）。查找都要将数组无限细分。
效率比暴力查找高，但使用场景也有限：数组必须有序！
// 递归法
public class Bisect{
public int bisect(int[] arr, int target, int lo, int hi){
int mid = lo + (hi - lo) / 2;
if (arr[mid] > target)
return bisect(arr, target, lo, mid - 1);
else if (arr[mid] < target)
return bisect(arr, target, mid + 1, hi);
else
return mid;
}
}
网友评论