Java数据结构和算法相关面试题

---

天行健，君子以自强不息；地势坤，君子以厚德载物。

---

每个人都有惰性，但不断学习是好好生活的根本，共勉！

---

文章均为学习整理笔记，分享记录为主，如有错误请指正，共同学习进步。

---

《送别》
寻阳五溪水，沿洄直入巫山里。胜境由来人共传，
君到南中自称美。送君别有八月秋，飒飒芦花复益愁。
云帆望远不相见，日暮长江空自流。

---

---

数据结构和算法

1. 时间复杂度和空间复杂度

时间复杂度和空间复杂度是衡量一个算法是否高效的重要标准
时间复杂度不是算法执行的时间，这是错误的

1.1 时间复杂度

指的是算法语句执行的次数，如O(1), O(n), O(logn), O(n2)

1.2 空间复杂度

指的是一个算法在运行过程中临时占用的存储空间大小，即被创建次数最多的变量被创建了多少次，这个算法的空间复杂度就是多少
如果算法语句中就有创建对象，那么该算法的时间复杂度和空间复杂度一般一致
算法语句被执行了多少次就创建了多少个对象

2. 数组和链表的结构对比

2.1 数组

概念

相同数据类型的元素按一定顺序排列的集合
就是把有限个类型相同的变量用一个名字，改名字就是数组名，用编号区分数组中变量，编号就是下标

数组的特性

• 数组必须先定义固定长度，不能动态适应数据动态增减
• 当数据增加时，可能超出原先定义的元素个数，当数据减少时，造成内存浪费
• 数据查询比较方便，根据下标就可以直接找到元素，时间复杂度O(1)，增加和删除比较复杂，需要移动操作数所在位置后的所有数据，时间复杂度为O(N)

2.2 链表

概念

一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

链表的特性

• 链表动态进行存储分配，可适应数据动态增减
• 插入、删除数据比较方便，时间复杂度为O(1),查询必须从头开始找起，时间复杂度为O(N)，相当麻烦

常见的链表

• 单链表，链表每一个元素都要保存一个指向下一个元素的指针
• 双链表，每个元素既要保存到下一个元素的指针，还要保存一个上一个元素的指针
• 循环链表，在最后一个元素中下一个元素指针指向首元素

链表和数组都是在堆里分配内存

应用

快速访问数据，较少或不插入和删除元素时，用数组更好
较多插入和删除元素时，使用链表数据结构更高效

3. 遍历一个树

四个遍历概念

• 先序遍历，先访问根节点，再访问左子树，最后访问右子树
• 后序遍历，先左子树，再右子树，最后根节点
• 中序遍历，先左子树，再根节点，最后右子树
• 层序遍历，每一层从左到右访问每一个节点

每一个子树遍历时依然按照此时的遍历顺序，可以采用递归实现遍历

4. 冒泡排序 Bubble Sort

4.1 算法描述

• 比较相邻的元素，第一个比第二个大，则交换两个元素位置
• 对每一个相邻元素作同样的工作，从开始第一对到结尾的最后一对，在最后的元素应该会是最大的数
• 对所有元素重复以上操作，除了最后一个元素
• 重复前面三个步骤，直到排序完成

4.2 复杂度

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
冒泡排序	O(n2)，2在n的右上角标	O(n2)，2在n的右上角标	O(n)	O(1)	稳定

如果两个元素相等，不会再交换位置，所以冒泡排序是一种稳定排序算法

4.3 代码实现

冒泡排序

public class BubbleSort{public static void bubbleSort(int[] arr){for(int i = 0; i< arr.length-1; i++){for(int j = 0; j< arr.length-i-1; j++){if(arr[j] > arr[j+1]){//当前面的值大于后面的值，交换位置int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}public static void main(String[] args){int[] arr = {4,2,5,1,9,3};bubbleSort(arr);for(int i : arr){System.out.print(i+"");}}
}

5. 快速排序 Quick Sort

5.1 算法描述

使用分治法将一串list分为两个子串sub-list，具体如下

• 从数列中挑出一个元素，称为基准pivot
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任意一边）。在这个分区退出后，该基准数处于数列的中间位置，这个称为分区操作partition
• 递归地rcursive将小于基准值元素的子数列和大于基准值元素的子数列排序

5.2 复杂度

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
快速排序	O(nlog2n),2在log右下角标	O(n2)， 2在n的右上角标	O(nlog2n)， 2在log右下角标	O(nlog2n)， 2在log右下角标	稳定

key值的选取可以有多种形式，例如中间数或随机数，分别会对算法的复杂度产生不同的影响

5.3 代码实现

快速排序

public class QuickSort{public static void quickSort(int[] data, int low, int high){int i,j,temp,t;if(low>high){return;}i = low;j = high;//temp为基准位temp = data[low];System.out.println("基准位："+temp);while(i<j){//先看右边，依次往左递减while(temp<=data[j]&&i<j){j--;}//再看左边，依次往右递增while(temp>=data[i]&&i<j){i++;}//如果满足条件则交换if(i<j){System.out.println("交换： "+data[i]+" 和 "+data[j]);t = data[j];data[j] = data[i];data[i] = t;System.out.println(java.util.Arrays.toString(data))}}//最后将基准位与i和j相等位置的数字互换System.out.println("基准位 "+temp+" 和i、j相遇的位置 "+data[i]+"交换");data[low] = data[i];data[i] = temp;System.out.println(java.util.Arrays.toString(data));//递归调用左半数组quickSort(data, low, j-1);//递归调用右半数组quickSort(data, j+1, high);}public static void main(String[] args){int[] data = {3, 44, 34, 5, 25, 58, 20, 1, 57, 23, 12, 60, 43};System.out.println("排序之前：\n"+java.util.Arrays.toString(data));quickSort(data, 0, data.length-1);System.out.println("排序之后：\n"+java.util.Arrays.toString(data));}}

6. 二分查找 Binary Search

6.1 算法描述

• 二分查找又称为折半查找，是一种效率较高的查找方法，要求列表中的元素是有序排列的，即如果未排序则必须先排序才可进行二分查找
• 假定表中元素按升序排序，将表中中间位置记录的关键字与查找的关键字进行比较，如果两者相等则查找成功
• 如果不相等，利用中间位置记录将表分成前后两个子表，如果中间位置记录的关键字大于所要查找的关键字，则进行查找前一个子表，否则就去查后一个子表
• 重复以上过程，知道找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功

6.2 复杂度

二分查找法
时间复杂度为O(log2n)
空间复杂度为O(1)

6.3 代码实现

二分法查找

public class BinarySearch{public static int binarySearch(int[] arr, int left, int right, int findValue){if(left>right){//递归推出条件， 找不到，返回-1return -1；}int midIndex = (left+right)/2;if(finaValue<arr[midIndex]>){//向左递归查找return binarySearch(arr, left, midIndex, findValue);}else if(findValue>arr[midIndex]){//向右递归查找return binarySearch(arr, midIndex, right, findValue);}else{return midIndex;}}public static void main(String[] args){//注意：需要对已排序的数组进行二分查找int[] data = {-40, -30, -12, -1, 2, 33, 38, 49, 50};int i = binarySearch(data, 0, data.length, 33);System.out.println(i);}
}

6.4 拓展

当有序数组中有多个相同的数值时，如何将所有的数值都查到

代码

public class BinarySearch2{public static List<Integer> binarySearch2(int[] arr, int left, int right, int findValue){List<Integer> list = new ArrayList<>();if(left>right){//递归退出条件，找不到，返回-1return list;}int midIndex = (left+right)/2;int midValue = arr[midIndex];if(findValue<midValue){//向左递归查找return binarySearch2(arr, left, mdiIndex-1, findValue);}else if(findValue>midValue){//向右递归查找return binarySearch2(arr, midIndex+1, right, findValue);}else{System.out.println("midIndex="+midIndex);//向左扫描int temp = midIndex-1;while(true){if(temp<0||arr[temp]!=findValue){break;}if(arr[temp]==findValue){list.add(temp);}temp -= 1;}//将中间这个索引加入list.add(midIndex);//向右边扫描temp = midIndex + 1;while(true){if(temp>arr.length-1||arr[temp]!=findValue){break;}if(arr[temp]==findValue){list.add(temp);}temp += 1;}return list;}}public static void main(String[] args){//注意： 需要对已排序的数组进行二分查找int[] data = {1, 4, 10, 58, 100, 1000, 1200, 1234, 1234, 3000, 4000};List<Integer> list = binarySearch2(data, 0, data.length, 1234);System.out.println(list);}
}

---

感谢阅读，祝君暴富！

---