百 M
数组
数组
数组是应用最广泛的数据存储结构，他被植入到大部分的编程语言中。数组比较简单，所以用它来作为介绍数据结构的起点。
数组（Array）是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按有序的形式组织起来的一种形式。这些有序排列的同类数据元素的集合称为数组。
数组是用于储存多个相同类型数据的集合。
Java中数组的基础知识
声明一个数组就是在内存空间中划出一串连续的空间
数组名代表的是连续空间的首地址，通过首地址可以依次访问数组所有元素，元素在数组中的排序位置叫下标，下标从零开始
数组长度一旦声明,不可改变不可追加
声明一个int类型的数组
int[ ] arr;或int arr[ ];
给数组分配空间
arr=new int[5];
给数组赋值
arr[0]=1; 0代表的是数组的第1个元素 ,元素下标为0
arr[1]=1; 1代表的是数组的第2个元素 ,元素下标为1
访问数组数据 ,使用数组下标访问 c=arr[4];
数组声明缩写
int[] arr={12,3,4,8,5,6,6,7,8,8,9,8};
int [] arr1=new int[ ]{12,3,4,8,5,6,6,4};
有序数组和无序数组
数组根据里面的内容是否有序，分为有序数组和无序数组
无序数组
- 增：在数组最后插入
- 删：找到元素；改为null；后面的元素逐一前移
- 查：从第一项元素开始遍历，直至找到该元素或者遍历结束
特点
- 效率：插入数据快，查找数据慢，删除数据慢
- 扩展性差：一旦创建后，大小就固定了，不能动态扩展数组元素的个数，有可能造成空间浪费或者空间不足。
有序数组
- 插入：找到插入元素应该插入的位置（根据元素值的大小）；将该位置以及以后的全部数据项向后移动一位；在该位置插入元素
- 删除：找到要删除的元素；后面的所有元素向前移位
- 查找：遍历查找or二分查找
特点
- 效率：插入数据慢，查找数据快（二分查找），删除数据慢。
- 扩展性差：一旦创建后，大小就固定了，不能动态扩展数组元素的个数，有可能造成空间浪费或者空间不足。
涉及到的算法
无序数组转换成有序数组
- 冒泡排序
- 选择排序
- 插入排序
- 直接插入排序
- 二分插入排序
- 链表插入排序
- 希尔排序
有序数组的查找
- 遍历查找
- 二分法查找
二分查找所需的比较次数
| 范围 | 所需比较次数 |
|---|---|
| 10 | 4 |
| 100 | 7 |
| 1000 | 10 |
| 10000 | 14 |
| 100000 | 17 |
| 1000000 | 20 |
| 10000000 | 24 |
| 100000000 | 27 |
| 1000000000 | 30 |
数据范围越大，二分查找体现出来的效率越好
| 比较次数(s) | 范围(N) | 由2的幂表示的范围() |
|---|---|---|
| 0 | 1 | |
| 1 | 2 | |
| 2 | 4 | |
| 3 | 8 | |
| 4 | 16 | |
| 5 | 32 | |
| 6 | 64 | |
| 7 | 128 | |
| 8 | 256 | |
| 9 | 512 | |
| 10 | 1024 |
设s表示次数，N表示范围则有如下方程
查找效率为
复杂度的大O表示法
- ：优秀。例如无序数组插入。
- ：良好。例如有序的二分查找。
- :及格。例如无序数组的删除，有序数组的删除和插入，线性查找。
- :不及格。例如冒泡排序。
总结有序数组和无序数组
有序数组：插入+ 查找 + 删除 = ;
无序数组：插入 + 查找 + 删除 = ;
所以在数据偏向查找操作的时候用有序数组快一些，在数据偏向插入的时候，无序数组好一些。删除操作效率一样
有序数组的最大的好处在于查找的时间复杂度是，而无序数组的时间复杂度是。
有序数组的缺点是插入的时间复杂度是，因为值大的元素需要往后移来给新元素腾位置，相反，无序数组的插入时间复杂度是常量
相关算法题
1 两数之和
在一个数组中找到两个数相加等于指定值，返回这两个值得位置
public class Solution {
public int[] twoSum (int[] numbers, int target) {
// write code here
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] == target) return new int[]{i + 1, j + 1};
}
}
return null;
}
}
2 返回集合的所有子集
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
Arrays.sort(S);
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
dfs(S, 0, res, new ArrayList<>());
return res;
}
private static void dfs(int[] s, int start, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
if (!res.contains(list)) res.add(new ArrayList<>(list));
for (int i = start; i < s.length; i++) {
list.add(s[i]);
dfs(s, i + 1, res, list);
list.remove(list.size() - 1);
}
}
}
3 加起来和为目标值得组合
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
if (num == null || num.length == 0 || target <= 0) return new ArrayList();
Arrays.sort(num);
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
dfs(num, target, 0, res, new ArrayList<Integer>());
return res;
}
private static void dfs(int[] num, int target, int start, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
// 计算和
int sum = 0;
if (list.size() > 0 && !res.contains(list)) {
for (int i = 0; i < list.size(); i++) {
sum += list.get(i);
}
}
if (sum == target) res.add(new ArrayList<>(list)); // 命中
else if (sum < target) {
for (int i = start; i < num.length; i++) {
list.add(num[i]);
dfs(num, target, i + 1, res, list);
list.remove(list.size() - 1);
}
}
}
}
4 合并两个有序数组
public class Solution {
public void merge(int A[], int m, int B[], int n) {
int res[] = new int[m + n];
int m1 = 0;
int n1 = 0;
while (m1 < m || n1 < n) {
if (m1 >= m) {
res[m1 + n1] = B[n1];
n1++;
} else if (n1 >= n) {
res[m1 + n1] = A[m1];
m1++;
} else if (A[m1] < B[n1]) {
res[m1 + n1] = A[m1];
m1++;
} else {
res[m1 + n1] = B[n1];
n1++;
}
}
for (int i = 0; i < m + n; i++) {
A[i] = res[i];
}
}
}
5 斐波那契数列
public class Solution {
// f[0] = 0; f[1] = 1; f[n] = f[n - 1] + f[n - 2];
public int Fibonacci(int n) {
if (n <= 1) return n;
int sum = 1;
int one = 0;
for (int i = 2; i <= n; i++) {
// f[n] = f[n - 1] + f[n - 2];
sum = sum + one;
// f[n - 1] = f[n] - f[n - 2];
one = sum - one;
}
return sum;
}
}
6 螺旋矩阵
import java.util.*;
public class Solution {
public ArrayList<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> res = new ArrayList<>();
if (matrix.length == 0) return res;
int top = 0;
int left = 0;
int bottom = matrix.length - 1;
int right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
// 1 上面 从左到右
for (int i = left; i <= right; i++) {
res.add(matrix[top][i]);
}
// 2 右面 从上到下
for (int i = top + 1; i <= bottom; i++) {
res.add(matrix[i][right]);
}
// 3 下面 从右到左 top == botom 时 在步骤1 时已处理过，不在重复处理
for (int i = right - 1; i >= left && top != bottom; i--) {
res.add(matrix[bottom][i]);
}
// 4 左面 从下到上 left == right 时 在步骤2时已处理过，不在重复处理
for (int i = bottom - 1; i >= top + 1 && left != right; i--) {
res.add(matrix[i][left]);
}
// 一圈走完 全部减1
top++;
right--;
bottom--;
left++;
}
return res;
}
}
7 矩阵查找
请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大
public class Solution {
/**
*
* @param matrix int整型二维数组
* @param target int整型
* @return bool布尔型
*/
public boolean searchMatrix (int[][] matrix, int target) {
// write code here
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
int start = 0;
int end = matrix.length * matrix[0].length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
int val = matrix[mid / matrix[0].length][mid % matrix[0].length];
if (val == target) return true;
if (val > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
}
8 数组中相加和为0的三元组
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
Arrays.sort(num);
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
int length = num.length;
for (int i = 0; i < length; i++) {
// 第一个数 num[i] 第二个数 num[mid] 第三个数 num[right]
int mid = i + 1;
int right = length - 1;
while (mid < right) {
int sum = num[i] + num[mid] + num[right];
if (sum == 0) {
ArrayList<Integer> temp = new ArrayList<>();
temp.add(num[i]);
temp.add(num[mid]);
temp.add(num[right]);
res.add(temp);
// 去重 mid = mid + 1 时 已经被记录，不能重复记录
while (mid + 1 < right && num[mid] == num[mid + 1]) mid++;
// 去重 right = right - 1 时 已经被记录，不能重复记录
while (right - 1 > mid && num[right - 1] == num[right]) right--;
mid++;
right--;
} else if (sum > 0) {
// 结果太大
right--;
} else mid++; // 结果太小
}
// 第一个数去重
while (i < length - 2 && num[i + 1] == num[i]) i++;
}
return res;
}
}
9 缺失数字
import java.util.*;
public class Solution {
public int solve (int[] a) {
// write code here
int target = 0;
int left = 0;
int right = a.length - 1;
while (left < right) {
int mid = (right + left) >> 1;
if (mid == a[mid]) left = mid + 1; // 相等 说明不在左边
else if (mid < a[mid]) right = mid; // 小于 说明在左边
}
return left;
}
}
10 在转动过的有序数组中寻找目标
public class Solution {
public int search (int[] A, int target) {
// write code here
int left = 0;
int right = A.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] == target) return mid;
if (A[mid] >= A[left]) {
// 左侧有序
if (A[mid] > target && A[left] <= target) right = mid - 1;
else left = mid + 1;
} else {
// 右侧有序
if (A[mid] < target && A[right] >= target) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
}
11 买卖股票的最好时机
public class Solution {
public int maxProfit (int[] prices) {
// write code here
if (prices.length == 0) return 0;
int min = prices[0];
int max = 0;
for (int i = 1; i < prices.length; i++) {
min = Math.min(min, prices[i]);
max = Math.max(max, prices[i] - min);
}
return max;
}
}
12 两个相等的排序数组中找到上中位数
public class Solution {
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
// write code here
int a1 = 0, b1 = 0, mid = arr1.length;
int res = arr1[0] < arr1[0] ? arr1[0] : arr2[0];
while (a1 + b1 < mid) {
if (arr1[a1] < arr2[b1]) res = arr1[a1++];
else res = arr2[b1++];
}
return res;
}
}
13 矩阵的最小路径和
public class Solution {
public int minPathSum (int[][] matrix) {
// write code here
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
// 第一个数 啥都不做
if (i == 0 && j == 0) {}
// 第一行
else if (i == 0) matrix[0][j] = matrix[0][j] + matrix[0][j - 1];
// 第一列
else if (j == 0) matrix[i][0] = matrix[i][0] + matrix[i - 1][0];
else matrix[i][j] += Math.min(matrix[i - 1][j], matrix[i][j - 1]);
}
}
return matrix[matrix.length - 1][matrix[0].length - 1];
}
}
14 数组中未出现的最小正整数
public class Solution {
public int minNumberdisappered (int[] arr) {
// write code here
int min = 1;
int index = 0;
while (index < arr.length) {
if (arr[index] == min) {
min++;
index = 0;
} else index++;
}
return min;
}
}
15 合并区间
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
intervals.sort((a, b) -> a.start - b.start);
ArrayList<Interval> res = new ArrayList<>();
int i = 0;
int left = 0;
int right = 0;
while (i < intervals.size()) {
left = intervals.get(i).start;
right = intervals.get(i).end;
while (i < intervals.size() - 1 && right >= intervals.get(i + 1).start) {
right = Math.max(right, intervals.get(++i).end);
}
res.add(new Interval(left, right));
i++;
}
return res;
}
}
16 顺时针旋转矩阵
public class Rotate {
public int[][] rotateMatrix(int[][] mat, int n) {
// write code here
// 行编号列编号从0开始
// 顺时针 行编号 == 原列编号, 列编号 == 原行数 - 1 - 原行编号
int res[][] = new int[mat[0].length][mat.length];
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[i].length; j++) {
res[j][mat.length - 1 - i] = mat[i][j];
}
}
return res;
}
}
17 数组中的最长连续子序列
public class Solution {
public int MLS (int[] arr) {
// write code here
if (arr == null || arr.length == 0) return 0;
Arrays.sort(arr);
int max = 1;
int temp = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i - 1] + 1 == arr[i]) {
// 满足条件 获取最大值
max = Math.max(max, ++temp);
} else if (arr[i - 1] == arr[i]) continue; // 前后相等 跳过
else temp = 1; // 重新计数
}
return max;
}
}
18 寻找最后的山峰
山峰元素是指其值大于或等于左右相邻值的元素。给定一个输入数组nums，任意两个相邻元素值不相等，数组可能包含多个山峰。找到索引最大的那个山峰元素并返回其索引。
public class Solution {
public int solve (int[] a) {
// write code here
if (a == null || a.length == 0) return -1;
for (int i = a.length - 1; i >= 1; i--) {
if (a[i] >= a[i - 1]) return i;
}
return 0;
}
}