数组

2021-01-28 15:15:34
117
参与编辑
版本 2

数组

数组是应用最广泛的数据存储结构,他被植入到大部分的编程语言中。数组比较简单,所以用它来作为介绍数据结构的起点。

数组(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的幂表示的范围(2s2^s)
0 1 202^0
1 2 212^1
2 4 222^2
3 8 232^3
4 16 242^4
5 32 252^5
6 64 262^6
7 128 272^7
8 256 282^8
9 512 292^9
10 1024 2102^10

设s表示次数,N表示范围则有如下方程

N=2sN = 2^s

s=log2Ns = log_2^N

查找效率为O(longN)O(long^N)

复杂度的大O表示法

  • O(1)O(1):优秀。例如无序数组插入。
  • O(logN)O(log^N):良好。例如有序的二分查找。
  • O(N)O(N):及格。例如无序数组的删除,有序数组的删除和插入,线性查找。
  • O(N2)O(N^2):不及格。例如冒泡排序。

总结有序数组和无序数组

有序数组:插入+ 查找 + 删除 = O(N)+O(logN)+O(N)O(N) + O(log^N) + O(N);

无序数组:插入 + 查找 + 删除 = O(1)+O(N)+O(N)O(1) + O(N) + O(N);

所以在数据偏向查找操作的时候用有序数组快一些,在数据偏向插入的时候,无序数组好一些。删除操作效率一样

有序数组的最大的好处在于查找的时间复杂度是O(logn)O(log^n),而无序数组的时间复杂度是O(n)O(n)

有序数组的缺点是插入的时间复杂度是O(n)O(n),因为值大的元素需要往后移来给新元素腾位置,相反,无序数组的插入时间复杂度是常量O(1)O(1)

相关算法题

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; } }

相似文章(系统自动检测得出)

  • 数组 51.45% 庶卒 2020-12-26
  • 算法 5.39% 庶卒 2020-12-23
  • 数据结构与算法综述 2.09% 庶卒 2021-01-26
  • 链表 2.08% 庶卒 2020-12-23
  • Java集合 0.72% 庶卒 2020-11-24
  • SAAS权限管理系统| 从产品到微服务接口的设计与实现 0.48% 庶卒 2020-11-15
  • 数据结构与算法 0.20% 游客333 2021-01-11
  • 多线程 0.17% 庶卒 2020-11-24
  • 标签