衡量复杂性：大 O 表示法
使用[大 O 表示法]是 Java 面试官将检查的一项基本技能。在我们进入一些更深入的示例之前，我们将首先通过一些问题来测试您对大 O 表示法的知识和理解。
作为复习，Big O 用于根据算法的运行时间和空间需求如何随输入大小增长对算法进行分类。
1：带加法的嵌套循环的大 O
问题陈述：
计算下面给出的代码片段的 Big O 复杂度。
class NestedLoop { public static void main(String[] args) { int n = 10; int sum = 0; double pie = 3.14; for (int var = 1; var < n; var = var + 3) { System.out.println("Pie: " + pie); for (int j = 1; j < n; j = j + 2) { sum++; } System.out.println("Sum = " + sum); } } } 复制代码
解：O(n 2 )
解决方案分解：
第 7 行的第一个 for 循环可以分解为 3 个部分：
- 初始化
- 比较
- 递增
由于初始化(int var = 0)在整个程序中只发生一次，因此需要一个时间单位。比较 ( var < n) 执行 (n/3+ 1) 次，增量运行n/3次。
类似地，( int j = 0) 运行n/3次，比较 ( j < n) 运行n/3 * (n/2 + 1) ，增量 ( )在外循环的每次迭代中j = j + 2执行n/2次，因此它运行：
网络异常，图片无法展示
|
下面逐行计算时间复杂度：
网络异常，图片无法展示
|
最后，我们添加所有行的时间复杂度，删除主要常量和低阶项，并找到我们的大 O 复杂度。
排序和搜索：快速排序、二分搜索等
几乎每个面试官都会问一个至少需要一种类型的搜索或排序的问题，如果不是更多的话。为了帮助您为这些问题做好准备，我们提供了以下概述部分来帮助您熟练掌握基础搜索/排序算法。
注意： 不太可能会提示您在面试中使用某种算法。相反，您必须学会根据问题陈述中的关键字来识别使用哪种算法。
在练习时，试着找出问题陈述的哪一部分会引导你使用指定的算法。
2：快速排序
问题陈述：
给定一个未排序的数字数组，找到K其中最小的数字。
请注意，它是K排序顺序中第 th 个最小的数字，而不是第Kth 个不同的元素。
import java.util.*; class KthSmallestNumber { public static int findKthSmallestNumber(int[] nums, int k) { // TODO: Write your code here return -1; } public static void main(String[] args) { int result = KthSmallestNumber.findKthSmallestNumber(new int[] { 1, 5, 12, 2, 11, 5 }, 3); System.out.println("Kth smallest number is: " + result); // since there are two 5s in the input array, our 3rd and 4th smallest numbers should be a '5' result = KthSmallestNumber.findKthSmallestNumber(new int[] { 1, 5, 12, 2, 11, 5 }, 4); System.out.println("Kth smallest number is: " + result); result = KthSmallestNumber.findKthSmallestNumber(new int[] { 5, 12, 11, -1, 12 }, 3); System.out.println("Kth smallest number is: " + result); } } 复制代码
解决方案：
import java.util.*; class KthSmallestNumber { public static int findKthSmallestNumber(int[] nums, int k) { return findKthSmallestNumberRec(nums, k, 0, nums.length - 1); } public static int findKthSmallestNumberRec(int[] nums, int k, int start, int end) { int p = partition(nums, start, end); if (p == k - 1) return nums[p]; if (p > k - 1) // search lower part return findKthSmallestNumberRec(nums, k, start, p - 1); // search higher part return findKthSmallestNumberRec(nums, k, p + 1, end); } private static int partition(int[] nums, int low, int high) { if (low == high) return low; int pivot = nums[high]; for (int i = low; i < high; i++) { // all elements less than 'pivot' will be before the index 'low' if (nums[i] < pivot) swap(nums, low++, i); } // put the pivot in its correct place swap(nums, low, high); return low; } private static void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } public static void main(String[] args) { int result = KthSmallestNumber.findKthSmallestNumber(new int[] { 1, 5, 12, 2, 11, 5 }, 3); System.out.println("Kth smallest number is: " + result); // since there are two 5s in the input array, our 3rd and 4th smallest numbers should be a '5' result = KthSmallestNumber.findKthSmallestNumber(new int[] { 1, 5, 12, 2, 11, 5 }, 4); System.out.println("Kth smallest number is: " + result); result = KthSmallestNumber.findKthSmallestNumber(new int[] { 5, 12, 11, -1, 12 }, 3); System.out.println("Kth smallest number is: " + result); } } 复制代码
解决方案分解：
时间复杂度： 平均O(N) 或最坏情况 O(n 2 )
我们使用 Quicksort 的分区方案来找到第 K 个最小的数字。我们递归地对输入数组进行分区，如果分区后我们的主元在索引处K-1，我们就找到了所需的数字。如果没有，我们选择以下选项之一：
- 如果枢轴的位置大于 K-1，我们递归地根据低于枢轴的数字对数组进行分区。
- 如果枢轴的位置小于 K-1，我们递归地根据大于枢轴的数字对数组进行分区。
3：二分查找
问题陈述：
我们得到一个二维数组，其中任何单独的行或列中的所有元素都已排序。在这样的矩阵中，我们必须搜索或找到给定键的位置。
class searchMatrix{ public static IntPair search_in_matrix(int matrix[][], int value) { //TODO: Write - Your - Code return new IntPair(-1, -1); } } 复制代码
解决方案：
class searchMatrix{ public static IntPair search_in_matrix(int matrix[][], int value) { int M = matrix.length; //rows int N = matrix[0].length; // columns // Let's start searching from top right. // Alternatively, searching from bottom left // i.e. matrix[M-1][0] can also work. int i = 0, j = N-1; while (i < M && j >= 0) { if (matrix[i][j] == value) { return new IntPair(i, j); } else if (value < matrix[i][j]) { // search left --j; } else { // search down. ++i; } } return new IntPair(-1, -1); } public static void verify_search(int [][] matrix) { for (int i = 0; i < matrix.length; ++i) { for (int j = 0; j < matrix[0].length; ++j) { System.out.println("Verifying at " + i + ", " + j); IntPair val_loc = search_in_matrix(matrix, matrix[i][j]); assert(val_loc.first == i); assert(val_loc.second == j); } } } public static void main(String[] args) { int [] [] matrix = new int [] [] { {1, 5, 45, 80, 81}, {6, 7, 48, 82, 83}, {20, 22, 49, 85, 86}, {21, 23, 50, 90, 92} }; verify_search(matrix); } } 复制代码
解决方案分解：
时间复杂度： O(m + n)
我们从矩阵的右上角开始，将其值与键进行比较。如果它们相等，我们就找到了钥匙的位置。
如果键小于当前元素，我们向左移动一个位置。如果键大于当前元素，我们向右移动一个位置。
当矩阵被排序时，向左移动总是导致比当前值更低的值，而向下移动总是导致更高的值。
我们继续这个过程，直到找到元素或超出矩阵的边界（这表明键不存在）。
4.归并排序
问题陈述：
给定链表的头指针，使用归并排序对链表进行升序排序，并返回排序后的链表的新头指针。
class MergeSort{ public static LinkedListNode mergeSort(LinkedListNode head) { //TODO: Write - Your - Code return head; } } 复制代码
解决方案：
class MergeSort{ // this method splits linked list in half by iterating over whole list // then returns head pointers of first and second halves of linked lists in firstSecond // The head of 1st half is just the head node of the linked list public static void splitInHalf(LinkedListNode head, Pair<LinkedListNode,LinkedListNode> firstSecond) { if (head == null) { return; } // Edge case: only one elements if (head.next == null) { firstSecond.first = head; firstSecond.second = null; } else { // We'll use the technique of moving two pointers: // 'fast' and 'slow'. 'fast' will move two steps in each // iteration where 'slow' will be pointing to middle element // at the end of loop. LinkedListNode slow, fast; slow = head; fast = head.next; while (fast != null) { fast = fast.next; if (fast != null) { fast = fast.next; slow = slow.next; } } firstSecond.first = head; firstSecond.second = slow.next; // Terminate first linked list. slow.next = null; } } public static LinkedListNode mergreSortedLists(LinkedListNode first, LinkedListNode second) { if (first == null) { return second; } else if (second == null) { return first; } LinkedListNode newHead; if (first.data <= second.data) { newHead = first; first = first.next; } else { newHead = second; second = second.next; } LinkedListNode newCurrent = newHead; while (first != null && second != null) { LinkedListNode temp = null; if (first.data <= second.data) { temp = first; first = first.next; } else { temp = second; second = second.next; } newCurrent.next = temp; newCurrent = temp; } if (first != null) { newCurrent.next = first; } else if (second != null) { newCurrent.next = second; } return newHead; } public static LinkedListNode mergeSort(LinkedListNode head) { // No need to sort a single element. if (head == null || head.next == null) { return head; } Pair<LinkedListNode,LinkedListNode> firstSecond = new Pair<LinkedListNode,LinkedListNode>(null,null); // Splits the list in half, sorts the sublists // and then merge the sorted lists for printing. splitInHalf(head, firstSecond); firstSecond.first = mergeSort(firstSecond.first); firstSecond.second = mergeSort(firstSecond.second); return mergreSortedLists(firstSecond.first, firstSecond.second); } public static void main(String[] args) { int[] v1 = {29, 23, 82, 11, 4, 3, 21}; LinkedListNode listHead1 = LinkedList.createLinkedList(v1); System.out.print("Unsorted list: "); LinkedList.display(listHead1); listHead1 = mergeSort(listHead1); System.out.print("Sorted list: "); LinkedList.display(listHead1); } } 复制代码
解决方案分解：
时间复杂度： O(nlogn)
在划分步骤中，我们将输入链表分成两半并一直这样做，直到有一个大小为 1 或 0 的链表。大小为 1 和 0 的链表总是排序的。在组合步骤中，我们合并排序列表并继续这样做，直到我们有一个完全排序的列表。
在每一步，我们将问题分成两个子问题。每个子问题的大小为n/2，合并步骤（合并排序列表）的总成本为n。
5.插入排序
问题陈述：
给定链表的头指针，使用插入排序对链表进行升序排序。返回排序链表的新头指针。
class InsertionSort{ public static LinkedListNode insertionSort(LinkedListNode head) { //TODO: Write - Your - Code return head; } } 复制代码
解决方案：
class InsertionSort{ public static LinkedListNode sortedInsert(LinkedListNode head, LinkedListNode node) { if (node == null) { return head; } if (head == null || node.data <= head.data) { node.next = head; return node; } LinkedListNode curr = head; while (curr.next != null && (curr.next.data < node.data)) { curr = curr.next; } node.next = curr.next; curr.next = node; return head; } public static LinkedListNode insertionSort(LinkedListNode head) { LinkedListNode sorted = null; LinkedListNode curr = head; while (curr != null) { LinkedListNode temp = curr.next; sorted = sortedInsert(sorted, curr); curr = temp; } return sorted; } public static void main(String[] args) { int[] list = {29, 23, 82, 11}; int[] listExpected = {11, 23, 29, 82}; LinkedListNode listHead = LinkedList.createLinkedList(list); LinkedListNode listHeadExpected = LinkedList.createLinkedList(listExpected); System.out.print("Original: "); LinkedList.display(listHead); listHead = insertionSort(listHead); System.out.print("After sorting: "); LinkedList.display(listHead); } } 复制代码
解决方案分解：
时间复杂度： O(n 2 )
虽然原始列表不为空：
- 从原始列表中删除一个元素（例如“X”）。
- 在排序列表中的正确排序位置插入“X”。
要将节点插入排序链表，我们可能需要根据插入的节点扫描整个排序列表。
6.哈希表
问题陈述：
使用 HashMap，实现一个函数，该函数将一个数组arr、一个数字value和数组的大小作为输入，并返回两个加起来为 的数字value。
class CheckSum { public static int[] findSum(int[] arr, int n) { int[] result = new int[2]; // write your code here return result; // return the elements in the array whose sum is equal to the value passed as parameter } } 复制代码
解决方案：
class CheckSum { public static int[] findSum(int[] arr, int n) { int[] result = new int[2]; HashMap < Integer, Boolean > hmap = new HashMap < Integer, Boolean > (); // Create a hashmap for (int i = 0; i < arr.length; i++) { hmap.put(n - arr[i], true); // Store value - arr[i] for all elements in arr } for (int i = 0; i < arr.length; i++) { if (hmap.containsKey(arr[i])) // If a value from arr is present in hmap { result[0] = arr[i]; result[1] = n - arr[i]; return result; } } return result; } public static void main(String args[]) { int n = 9; int[] arr1 = {2, 4, 5, 7, 8}; int[] arr2 = findSum(arr1, n); int num1 = arr2[0]; int num2 = arr2[1]; if ((num1 + num2) != n) System.out.println("Results not found!"); else System.out.println("Sum of " + n + " found: " + num1 + " and " + num2); } } 复制代码
解决方案分解：
时间复杂度： O(n)
对于数组中的所有元素arr，我们将差异存储n - arr[i]在 中hmap。
然后通过对 的另一次迭代，我们检查中arr是否存在任何元素，这意味着和找到的数字 ( )的差值也存在。arr``hmap``n``n - arr[i]
因此，创建了一个名为 2 的数组result来存储总和为 的对n。如果hmap包含数组元素，result[]则更新，否则返回包含默认值。
7.哈希集
问题陈述：
实现一个isSubset()函数，将两个数组作为输入，并检查一个数组是否是另一个给定数组的子集。
class CheckSubset { public static boolean isSubset(int[] arr1, int[] arr2) { // write your code here return false; } } 复制代码
解决方案：
class CheckSubset { static boolean isSubset(int arr1[], int arr2[]) { HashSet<Integer> hset= new HashSet<>(); // hset stores all the values of arr1 for(int i = 0; i < arr1.length; i++) { if(!hset.contains(arr1[i])) hset.add(arr1[i]); } // loop to check if all elements of arr2 also // lies in arr1 for(int i = 0; i < arr2.length; i++) { if(!hset.contains(arr2[i])) return false; } return true; } public static void main(String args[]) { int[] arr1 = {9, 4, 7, 1, -2, 6, 5}; int[] arr2 = {7, 1, -2}; int[] arr3 = {10, 12}; System.out.println(isSubset(arr1, arr2)); System.out.println(isSubset(arr1, arr3)); } } 复制代码
解决方案分解：
时间复杂度： O(m+n)
首先，我们遍历arr2，arr3看是否能在 中找到它们的元素arr1。
在后端，这些值会根据它们在arr1.
