Java面试黄金宝典15

1. 请找出增序排列中一个数字第一次和最后一次出现的数组下标

定义

由于数组是增序排列的，我们可以利用二分查找的特性来高效地定位目标数字。对于查找第一次出现的位置，当中间元素等于目标数字时，我们需要继续向左搜索，以确保找到最左边的目标数字；对于查找最后一次出现的位置，当中间元素等于目标数字时，我们需要继续向右搜索，以确保找到最右边的目标数字。

要点

采用二分查找算法，其时间复杂度为 O(logn)，可以大大提高查找效率。
分别编写两个二分查找函数，一个用于查找第一次出现的位置，另一个用于查找最后一次出现的位置。

代码示例

java

public class FindFirstAndLastPosition {public static int[] searchRange(int[] nums, int target) {int first = findFirst(nums, target);int last = findLast(nums, target);return new int[]{first, last};}private static int findFirst(int[] nums, int target) {int left = 0, right = nums.length - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1;if (nums[mid] == target) {result = mid;}} else {left = mid + 1;}}return result;}private static int findLast(int[] nums, int target) {int left = 0, right = nums.length - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;if (nums[mid] == target) {result = mid;}} else {right = mid - 1;}}return result;}public static void main(String[] args) {int[] nums = {1, 2, 2, 2, 3, 4, 4, 5};int target = 2;int[] range = searchRange(nums, target);System.out.println("First position: " + range[0]);System.out.println("Last position: " + range[1]);}
}

应用

若数组不是严格增序，存在重复元素且可能有相等元素打乱顺序的情况，可先对数组进行排序，再使用上述方法。不过排序会增加额外的时间复杂度，如使用快速排序，时间复杂度为 O(nlogn)。

2. 如何实现海量数据去重

定义

哈希表：利用哈希表的特性，其键具有唯一性。将数据作为键插入哈希表中，重复的数据会自动覆盖，最终哈希表中的键即为去重后的数据。
位图（BitMap）：对于整数数据，位图是一个不错的选择。位图是一个二进制数组，每个位代表一个数据，通过设置相应位的值来标记数据的出现情况。

要点

哈希表适用于各种类型的数据，但需要较多的内存空间，空间复杂度为 O(n)。
位图适用于整数数据，内存占用较小，但数据范围不能太大。

代码示例（哈希表）

java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;public class MassiveDataDeduplication {public static List<Integer> deduplicate(List<Integer> data) {Set<Integer> set = new HashSet<>();List<Integer> result = new ArrayList<>();for (int num : data) {if (set.add(num)) {result.add(num);}}return result;}public static void main(String[] args) {List<Integer> data = List.of(1, 2, 2, 3, 4, 4, 5);List<Integer> deduplicatedData = deduplicate(data);System.out.println(deduplicatedData);}
}

应用

当数据量极大，无法全部加载到内存时，可采用分治策略。将数据分成多个小文件，分别对每个小文件进行去重，最后再合并结果。这样可以降低单次处理的数据量，避免内存溢出。

3. 如何找出海量数据中前 10 个最大的数（数据有重复）

定义

可以使用最小堆来解决该问题。首先创建一个大小为 10 的最小堆，将前 10 个数据插入堆中。然后遍历剩余的数据，如果当前数据大于堆顶元素，则将堆顶元素替换为当前数据，并调整堆，以保持最小堆的性质。最后堆中的元素就是前 10 个最大的数。

要点

最小堆的时间复杂度为 O(nlogk)，其中 n 是数据的总数，k 是要找的最大数的个数。
堆的插入和删除操作的时间复杂度为 O(logk)。

代码示例

java

import java.util.PriorityQueue;public class TopKNumbers {public static int[] topK(int[] nums, int k) {PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);for (int i = 0; i < nums.length; i++) {if (i < k) {minHeap.offer(nums[i]);} else if (nums[i] > minHeap.peek()) {minHeap.poll();minHeap.offer(nums[i]);}}int[] result = new int[k];for (int i = k - 1; i >= 0; i--) {result[i] = minHeap.poll();}return result;}public static void main(String[] args) {int[] nums = {3, 2, 1, 5, 6, 4};int k = 2;int[] topK = topK(nums, k);for (int num : topK) {System.out.print(num + " ");}}
}

应用

可以考虑使用分布式算法，将数据分散到多个节点上，每个节点找出自己的前 10 个最大的数，然后将这些结果合并，再找出最终的前 10 个最大的数。这样可以充分利用分布式系统的并行计算能力，提高处理效率。

4. 数组先升序在降序，找出最大数

定义

由于数组先升序后降序，我们可以使用二分查找来找到最大数。通过比较中间元素和其相邻元素的大小，来判断最大数在左半部分还是右半部分。

要点

二分查找的时间复杂度为 O(logn)，可以高效地找到最大数。
比较中间元素和其相邻元素的大小，以此来确定最大数的位置。

代码示例

java

public class FindMaxInAscDescArray {public static int findMax(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < nums[mid + 1]) {left = mid + 1;} else {right = mid;}}return nums[left];}public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5, 4, 3, 2, 1};int max = findMax(nums);System.out.println("Max number: " + max);}
}

应用

若数组中有重复元素，需要对二分查找的条件进行适当调整。例如，当中间元素与其相邻元素相等时，需要进一步判断左右两侧的趋势。

5. 正整数数组，如何拼出一个最大的正数

定义

自定义排序规则，将数组中的元素进行排序。排序规则是将两个元素拼接成两个字符串，比较这两个字符串的大小，将拼接后较大的字符串对应的元素排在前面。

要点

自定义排序规则，使用 Comparator 接口。
将元素拼接成字符串进行比较。

代码示例

java

import java.util.Arrays;
import java.util.Comparator;public class LargestNumber {public static String largestNumber(int[] nums) {String[] strs = new String[nums.length];for (int i = 0; i < nums.length; i++) {strs[i] = String.valueOf(nums[i]);}Arrays.sort(strs, new Comparator<String>() {@Overridepublic int compare(String s1, String s2) {return (s2 + s1).compareTo(s1 + s2);}});if (strs[0].equals("0")) {return "0";}StringBuilder sb = new StringBuilder();for (String str : strs) {sb.append(str);}return sb.toString();}public static void main(String[] args) {int[] nums = {3, 30, 34, 5, 9};String largest = largestNumber(nums);System.out.println("Largest number: " + largest);}
}

应用

若数组中包含负数，需要先将负数进行处理，例如将负数转换为正数，或者在排序时单独处理负数。

6. 一个正整数数组，给其中一个数字加 1，使得所有数乘积最大，找出加 1 的那个数字

定义

遍历数组，计算给每个数字加 1 后的所有数的乘积，找出乘积最大时对应的数字。

要点

遍历数组，计算每种情况下的乘积。
记录最大乘积和对应的数字下标。

代码示例

java

public class MaxProductAfterIncrement {public static int findNumberToIncrement(int[] nums) {int maxProduct = Integer.MIN_VALUE;int index = -1;for (int i = 0; i < nums.length; i++) {int product = 1;for (int j = 0; j < nums.length; j++) {if (j == i) {product *= (nums[j] + 1);} else {product *= nums[j];}}if (product > maxProduct) {maxProduct = product;index = i;}}return index;}public static void main(String[] args) {int[] nums = {1, 2, 3};int index = findNumberToIncrement(nums);System.out.println("Index of number to increment: " + index);}
}

应用

可以考虑优化算法，通过数学推导找出更高效的方法。例如，分析数组元素的大小关系，找出对乘积影响最大的元素。

7. 手写快排、堆排二分查找

快速排序

java

public class QuickSort {public static void quickSort(int[] nums, int left, int right) {if (left < right) {int pivotIndex = partition(nums, left, right);quickSort(nums, left, pivotIndex - 1);quickSort(nums, pivotIndex + 1, right);}}private static int partition(int[] nums, int left, int right) {int pivot = nums[right];int i = left - 1;for (int j = left; j < right; j++) {if (nums[j] < pivot) {i++;swap(nums, i, j);}}swap(nums, i + 1, right);return i + 1;}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[] nums = {3, 2, 1, 5, 6, 4};quickSort(nums, 0, nums.length - 1);for (int num : nums) {System.out.print(num + " ");}}
}

堆排序

java

public class HeapSort {public static void heapSort(int[] nums) {int n = nums.length;// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(nums, n, i);}// 一个个交换元素for (int i = n - 1; i > 0; i--) {// 将堆顶元素（最大值）与当前未排序部分的最后一个元素交换int temp = nums[0];nums[0] = nums[i];nums[i] = temp;// 重新调整堆heapify(nums, i, 0);}}private static void heapify(int[] nums, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;// 如果左子节点大于根节点if (left < n && nums[left] > nums[largest]) {largest = left;}// 如果右子节点大于当前最大节点if (right < n && nums[right] > nums[largest]) {largest = right;}// 如果最大节点不是根节点if (largest != i) {int swap = nums[i];nums[i] = nums[largest];nums[largest] = swap;// 递归调整受影响的子树heapify(nums, n, largest);}}public static void main(String[] args) {int[] nums = {3, 2, 1, 5, 6, 4};heapSort(nums);for (int num : nums) {System.out.print(num + " ");}}
}

二分查找

java

public class BinarySearch {public static int binarySearch(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5};int target = 3;int index = binarySearch(nums, target);System.out.println("Index of target: " + index);}
}

8. 手写单词接龙的程序

java

import java.util.*;public class WordChain {public static boolean isValidChain(List<String> words) {if (words.size() <= 1) {return true;}for (int i = 1; i < words.size(); i++) {String prev = words.get(i - 1);String curr = words.get(i);if (prev.charAt(prev.length() - 1) != curr.charAt(0)) {return false;}}return true;}public static void main(String[] args) {List<String> words = Arrays.asList("apple", "elephant", "tiger");boolean isValid = isValidChain(words);System.out.println("Is valid chain: " + isValid);}
}

9. 如何实现括号匹配

定义

使用栈来实现括号匹配。遍历字符串，遇到左括号时将其压入栈中，遇到右括号时，检查栈顶元素是否为对应的左括号，如果是则弹出栈顶元素，否则返回不匹配。最后检查栈是否为空，如果为空则匹配成功。

要点

使用栈来存储左括号。
遍历字符串，根据括号类型进行相应的操作。

代码示例

java

import java.util.Stack;public class BracketMatching {public static boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if (c == '(' || c == '[' || c == '{') {stack.push(c);} else {if (stack.isEmpty()) {return false;}char top = stack.pop();if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {return false;}}}return stack.isEmpty();}public static void main(String[] args) {String s = "()[]{}";boolean isValid = isValid(s);System.out.println("Is valid: " + isValid);}
}

应用

可以考虑处理多种类型的括号嵌套的情况，以及处理包含其他字符的字符串。在处理时，需要忽略非括号字符，只对括号进行匹配检查。

10. 一个数组存着负数与正数，将正数放在前面，负数放在后面

定义

使用双指针法，一个指针从左往右遍历，一个指针从右往左遍历。当左指针指向负数，右指针指向正数时，交换两个指针所指的元素。

要点

使用双指针，时间复杂度为 O(n)。
交换元素的位置。

代码示例

java

public class RearrangeArray {public static void rearrange(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {while (left < right && nums[left] > 0) {left++;}while (left < right && nums[right] < 0) {right--;}if (left < right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}}}public static void main(String[] args) {int[] nums = {1, -2, 3, -4, 5};rearrange(nums);for (int num : nums) {System.out.print(num + " ");}}
}