1. 如何找一个无序数组第 K 大的元素
java
import java.util.Arrays;
public class KthLargestElement {
public static int findKthLargest(int[] nums, int k) {
int left = 0, right = nums.length - 1;
k = nums.length - k;
while (left < right) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == k) {
break;
} else if (pivotIndex < k) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
return nums[k];
}
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};
int k = 2;
System.out.println(findKthLargest(nums, k));
}
}
- 定义
快速选择算法是一种从无序列表中找到第 k 小（或第 k 大）元素的选择算法。它与快速排序算法有关，利用了快速排序中分区的思想，通过不断缩小搜索范围，只在包含目标元素的那一部分继续进行分区操作，从而避免对整个数组进行排序。
- 要点
- 平均时间复杂度为 O(n)，最坏情况为 O(n2)。
- 分区函数是核心，它将数组分为两部分，左边部分小于等于基准值，右边部分大于基准值。
- 应用
- 数据分析：在海量数据中找出排名前 k 的数据，如找出销售额排名前 10 的商品。
- 游戏开发：在游戏中根据玩家的得分找出排名前 k 的玩家。
2. 找出数组两个数的和等于给定的数
java
import java.util.HashMap;
import java.util.Map;
public class TwoSum {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{};
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println(Arrays.toString(result));
}
}
- 定义
通过哈希表存储数组元素及其下标，在遍历数组时，对于每个元素，检查哈希表中是否存在目标值减去当前元素的差值。若存在，则找到了两个数的和等于给定的数。
- 要点
- 时间复杂度为 O(n)，因为只需要遍历一次数组。
- 空间复杂度为 O(n)，主要用于存储哈希表。
- 应用
- 购物系统：在商品价格列表中找出两件商品价格之和等于给定预算的组合。
- 密码学：在密钥对中寻找满足特定和关系的密钥组合。
3. 无序数组找中位数（时间复杂度为 O(n) ）
java
public class MedianOfUnsortedArray {
public static double findMedian(int[] nums) {
int n = nums.length;
if (n % 2 == 1) {
return findKthSmallest(nums, n / 2);
} else {
return (findKthSmallest(nums, n / 2 - 1) + findKthSmallest(nums, n / 2)) / 2.0;
}
}
private static int findKthSmallest(int[] nums, int k) {
int left = 0, right = nums.length - 1;
while (left < right) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == k) {
break;
} else if (pivotIndex < k) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
return nums[k];
}
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, 4, 5};
System.out.println(findMedian(nums));
}
}
- 定义
中位数是按顺序排列的一组数据中居于中间位置的数，如果数据有奇数个，则正中间的数字为中位数；如果数据有偶数个，则中间两位数的平均数为中位数。通过快速选择算法找到无序数组中间位置的元素来计算中位数。
- 要点
- 平均时间复杂度为 O(n)，最坏情况为 O(n2)。
- 分区函数是关键，它将数组分为两部分，左边小于等于基准值，右边大于基准值。
- 应用
- 统计学：在分析数据的集中趋势时，中位数是一个重要的统计量。
- 机器学习：在数据预处理阶段，中位数可用于处理异常值。
4. 两个有序数组找中位数（时间复杂度为 O(log(min(m,n))) ）
java
public class MedianOfTwoSortedArrays {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int left = 0, right = m;
while (left <= right) {
int partition1 = (left + right) / 2;
int partition2 = (m + n + 1) / 2 - partition1;
int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
int minRight1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];
int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
int minRight2 = (partition2 == n) ? Integer.MAX_VALUE : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 == 0) {
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
} else {
return Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
right = partition1 - 1;
} else {
left = partition1 + 1;
}
}
throw new IllegalArgumentException("Input arrays are not sorted.");
}
public static void main(String[] args) {
int[] nums1 = {1, 3};
int[] nums2 = {2};
System.out.println(findMedianSortedArrays(nums1, nums2));
}
}
- 定义
通过二分查找在较短的数组上找到一个合适的分割点，使得两个数组分割后的左右两部分元素个数相等，并且左边部分的最大值小于等于右边部分的最小值，从而计算出两个有序数组的中位数。
- 要点
- 时间复杂度为 O(log(min(m,n)))，其中 m 和 n 分别是两个数组的长度。
- 要处理边界情况，如分割点在数组的开头或结尾。
- 应用
- 数据库查询：在合并两个有序数据集时，快速计算中位数以进行数据分析。
- 金融分析：在分析两个不同投资组合的收益数据时，计算中位数来评估整体表现。
5. 写大数加法代码
java
import java.math.BigInteger;
public class BigNumberAddition {
public static String addStrings(String num1, String num2) {
StringBuilder result = new StringBuilder();
int carry = 0;
int i = num1.length() - 1;
int j = num2.length() - 1;
while (i >= 0 || j >= 0 || carry != 0) {
int x = (i >= 0) ? num1.charAt(i--) - '0' : 0;
int y = (j >= 0) ? num2.charAt(j--) - '0' : 0;
int sum = x + y + carry;
result.append(sum % 10);
carry = sum / 10;
}
return result.reverse().toString();
}
public static void main(String[] args) {
String num1 = "123";
String num2 = "456";
System.out.println(addStrings(num1, num2));
}
}
- 定义
大数加法是指对超出基本数据类型表示范围的大整数进行加法运算。通过逐位相加并处理进位的方式来实现。
- 要点
- 要处理进位，确保每一位相加的结果正确。
- 要处理两个字符串长度不同的情况。
- 应用
- 密码学：在加密算法中，需要处理非常大的整数。
- 科学计算：在天文学、物理学等领域，经常需要处理极大的数值。
6. 输出二叉树从左边看过去能看到的所有节点
java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class LeftViewOfBinaryTree {
public static List<Integer> leftSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (i == 0) {
result.add(node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return result;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
List<Integer> result = leftSideView(root);
System.out.println(result);
}
}
- 定义
通过广度优先搜索（BFS）遍历二叉树的每一层，将每层的第一个节点记录下来，这些节点就是从左边看过去能看到的节点。
- 要点
- 使用队列来实现 BFS。
- 记录每层的节点个数，确保只取每层的第一个节点。
- 应用
- 图形渲染：在绘制树形结构的图形时，确定从左侧可见的节点。
- 文件系统遍历：在树形文件系统中，查找从左侧视角可见的目录或文件。
7. 算法题：给定一个翻转过的有序数组，找出翻转点的下标
java
public class FindPivotIndex {
public static int findPivot(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
public static void main(String[] args) {
int[] nums = {5, 6, 7, 8, 1, 2, 3};
System.out.println(findPivot(nums));
}
}
- 定义
利用二分查找的思想，通过比较中间元素和最右边元素的大小关系，不断缩小搜索范围，找到翻转点的下标。
- 要点
- 二分查找的时间复杂度为 O(logn)。
- 要注意边界条件的处理。
- 应用
- 数据恢复：在处理旋转过的有序数据时，找到旋转点以恢复原始顺序。
- 搜索算法优化：在旋转有序数组中进行搜索时，先找到旋转点可以提高搜索效率。
8. 给定一个整数数组，数组中元素无重复。和一个整数 limit，求数组元素全排列，要求相邻两个数字和小于 limit
java
import java.util.ArrayList;
import java.util.List;
public class PermutationsWithLimit {
public static List<List<Integer>> permute(int[] nums, int limit) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, limit, new ArrayList<>(), used, result);
return result;
}
private static void backtrack(int[] nums, int limit, List<Integer> path, boolean[] used, List<List<Integer>> result) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
if (!path.isEmpty() && path.get(path.size() - 1) + nums[i] >= limit) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtrack(nums, limit, path, used, result);
path.remove(path.size() - 1);
used[i] = false;
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
int limit = 4;
List<List<Integer>> result = permute(nums, limit);
System.out.println(result);
}
}
- 定义
使用回溯法生成数组的所有排列，在生成过程中检查相邻两个数字的和是否小于给定的 limit，如果不满足条件则跳过该排列。
- 要点
- 回溯法是一种通过尝试所有可能的组合来解决问题的方法。
- 使用布尔数组来记录元素是否已经被使用。
- 应用
- 任务调度：在安排任务顺序时，确保相邻任务的资源消耗之和不超过限制。
- 电路设计：在连接电子元件时，保证相邻元件的电压或电流之和不超过安全范围。
9. 算法题：行列都有序二维数组，找出指定元素的位置，扩展到三维数组呢
二维数组
java
public class SearchIn2DArray {
public static boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int rows = matrix.length;
int cols = matrix[0].length;
int i = 0;
int j = cols - 1;
while (i < rows && j >= 0) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
j--;
} else {
i++;
}
}
return false;
}
public static void main(String[] args) {
int[][] matrix = {
{1, 4, 7},
{2, 5, 8},
{3, 6, 9}
};
int target = 5;
System.out.println(searchMatrix(matrix, target));
}
}
- 定义
从二维数组的右上角开始，根据当前元素与目标元素的大小关系，向左或向下移动，直到找到目标元素或超出数组范围。
- 要点
- 时间复杂度为 O(m+n)，其中 m 和 n 分别是二维数组的行数和列数。
- 要注意边界条件的处理。
- 应用
- 图像处理：在二维像素矩阵中查找特定颜色值的像素。
- 数据库索引：在二维索引表中查找特定记录。
三维数组
java
public class SearchIn3DArray {
public static boolean search3DMatrix(int[][][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0 || matrix[0][0].length == 0) {
return false;
}
int x = matrix.length;
int y = matrix[0].length;
int z = matrix[0][0].length;
int i = 0;
int j = y - 1;
int k = z - 1;
while (i < x && j >= 0 && k >= 0) {
if (matrix[i][j][k] == target) {
return true;
} else if (matrix[i][j][k] > target) {
if (j > 0 && matrix[i][j - 1][k] >= target) {
j--;
} else {
k--;
}
} else {
i++;
}
}
return false;
}
public static void main(String[] args) {
int[][][] matrix = {
{
{1, 2, 3},
{4, 5, 6}
},
{
{7, 8, 9},
{10, 11, 12}
}
};
int target = 5;
System.out.println(search3DMatrix(matrix, target));
}
}
- 定义
从三维数组的某个角开始，根据元素的大小关系，在三个维度上进行移动，直到找到目标元素或超出数组范围。
- 要点
- 要根据元素大小灵活调整在三个维度上的移动方向。
- 注意边界条件的处理。
- 应用
- 医学成像：在三维医学图像数据中查找特定的组织或病变。
- 地理信息系统：在三维地理数据中查找特定的地理特征。
10. 输入指定个数的字符串，按照字符串长度进行排序，然后重新从短到长输出，排序算法要自己写不能用自带的
java
import java.util.Scanner;
public class SortStringsByLength {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入字符串的个数: ");
int n = scanner.nextInt();
scanner.nextLine(); // 消耗掉换行符
String[] strings = new String[n];
System.out.println("请输入字符串:");
for (int i = 0; i < n; i++) {
strings[i] = scanner.nextLine();
}
bubbleSort(strings);
System.out.println("排序后的字符串:");
for (String str : strings) {
System.out.println(str);
}
}
public static void bubbleSort(String[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j].length() > arr[j + 1].length()) {
// 交换 arr[j+1] 和 arr[j]
String temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
- 定义
冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。这里按照字符串的长度进行比较和交换。
- 要点
- 时间复杂度为 O(n2)。
- 要注意字符串长度的比较。
- 应用
- 文本处理：在对文章中的单词或句子按照长度进行排序时使用。
- 数据展示：在展示一组字符串数据时，按照长度排序以提高可读性。
友情提示：本文已经整理成文档，可以到如下链接免积分下载阅读