30個最常見算法題及其Java實現和詳細解析
前言
算法是計算機科學的核心，掌握常見算法問題對Java開發(fā)者至關重要。本文精選30個高頻算法題，附Java實現和詳細解析，助你提升編程和面試能力。
1. 兩數之和 (Two Sum)
?問題描述?：給定一個整數數組 nums和一個目標值 target，請在數組中找出和為目標值的兩個整數，并返回它們的數組下標。
?Java解答?：
public 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);
}
throw new IllegalArgumentException("No two sum solution");
}?解析?：使用哈希表?（HashMap）存儲元素值及其索引。對于每個元素，計算其與目標值的差值，檢查差值是否已在哈希表中。若存在，直接返回結果；否則將當前元素存入哈希表。?時間復雜度為O(n)?，空間復雜度為O(n)。
2. 反轉鏈表 (Reverse Linked List)
?問題描述?：反轉一個單鏈表。
?Java解答?：
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}?解析?：采用迭代法，使用三個指針prev、curr和nextTemp。遍歷鏈表時，將當前節(jié)點的next指針指向前一個節(jié)點，然后移動指針繼續(xù)處理，直到鏈表末尾。?時間復雜度O(n)?，空間復雜度O(1)。
3. 字符串判斷回文 (Valid Palindrome)
?問題描述?：判斷一個字符串是否是回文串?（只考慮字母和數字字符，忽略大小寫）。
?Java解答?：
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}?解析?：使用雙指針技術，一個從字符串開頭向右移動，一個從末尾向左移動。跳過非字母數字字符，比較字符是否相等（忽略大小寫）。?時間復雜度O(n)?，空間復雜度O(1)。
4. 合并兩個有序鏈表 (Merge Two Sorted Lists)
?問題描述?：將兩個升序鏈表合并為一個新的升序鏈表。
?Java解答?：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}?解析?：創(chuàng)建虛擬頭節(jié)點dummy簡化操作。比較兩鏈表當前節(jié)點值，將較小節(jié)點連接到新鏈表，直到某一鏈表遍歷完，最后將剩余部分直接鏈接。?時間復雜度O(n+m)?，空間復雜度O(1)。
5. 二分查找 (Binary Search)
?問題描述?：在排序數組中查找特定元素，返回其索引，未找到返回-1。
?Java解答?：
public 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;
}?解析?：?二分查找通過維護左右邊界，每次比較中間元素與目標值，縮小一半搜索范圍。?注意邊界條件?（left <= right）。?時間復雜度O(log n)?，空間復雜度O(1)。
6. 最大子序和 (Maximum Subarray)
?問題描述?：找出整數數組中連續(xù)子數組的最大和。
?Java解答?：
public int maxSubArray(int[] nums) {
int maxSoFar = nums[0];
int maxEndingHere = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}?解析?：使用Kadane算法。遍歷數組，對于每個元素，決定是將其加入當前子數組還是開始新的子數組。maxEndingHere記錄當前子數組和，maxSoFar記錄全局最大和。?時間復雜度O(n)?，空間復雜度O(1)。
7. 爬樓梯問題 (Climbing Stairs)
?問題描述?：每次可以爬1或2階臺階，有多少種不同方法爬到n階樓頂？
?Java解答?：
public int climbStairs(int n) {
if (n == 1) return 1;
int first = 1;
int second = 2;
for (int i = 3; i <= n; i++) {
int third = first + second;
first = second;
second = third;
}
return second;
}?解析?：這是動態(tài)規(guī)劃問題，本質是求斐波那契數列。定義狀態(tài)dp[i]為到達第i階的方法數，狀態(tài)轉移方程：dp[i] = dp[i-1] + dp[i-2]。使用滾動數組優(yōu)化空間。?時間復雜度O(n)?，空間復雜度O(1)。
8. 二叉樹的層序遍歷 (Binary Tree Level Order Traversal)
?問題描述?：返回二叉樹按層序遍歷的節(jié)點值。
?Java解答?：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(currentLevel);
}
return result;
}?解析?：使用隊列實現廣度優(yōu)先搜索（BFS）?。每次處理一層節(jié)點，將其子節(jié)點加入隊列。?時間復雜度O(n)?，空間復雜度O(n)。
9. 有效的括號 (Valid Parentheses)
?問題描述?：判斷字符串中的括號是否有效閉合。
?Java解答?：
public 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();
}?解析?：使用棧數據結構。遇到左括號入棧，遇到右括號檢查棧頂是否匹配。?時間復雜度O(n)?，空間復雜度O(n)。
10. 尋找數組中的重復數 (Find the Duplicate Number)
?問題描述?：給定包含1到n整數的數組，假設只有一個重復數，找出它。
?Java解答?：
public int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}?解析?：將數組視為鏈表，使用Floyd判圈算法?（快慢指針）。快指針每次兩步，慢指針每次一步，相遇后重置慢指針，兩指針同速前進，再次相遇點為重復數。?時間復雜度O(n)?，空間復雜度O(1)。
11. 二叉樹的最大深度 (Maximum Depth of Binary Tree)
?問題描述?：給定二叉樹，找出其最大深度。
?Java解答?：
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}?解析?：使用遞歸深度優(yōu)先搜索（DFS）。二叉樹的最大深度等于左右子樹最大深度加1。?時間復雜度O(n)?，空間復雜度O(h)（h為樹高）。
12. 最長遞增子序列 (Longest Increasing Subsequence)
?問題描述?：找出數組中最長嚴格遞增子序列的長度。
?Java解答?：
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int maxAns = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxAns = Math.max(maxAns, dp[i]);
}
return maxAns;
}?解析?：使用動態(tài)規(guī)劃。定義dp[i]為以第i個元素結尾的最長遞增子序列長度。對于每個元素，檢查之前所有元素，若當前元素更大，則更新dp[i]。?時間復雜度O(n²)?，空間復雜度O(n)。
13. 二叉樹的前序遍歷 (Binary Tree Preorder Traversal)
?問題描述?：返回二叉樹前序遍歷的節(jié)點值。
?Java解答?：
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return result;
}?解析?：使用棧模擬遞歸過程。前序遍歷順序為"根-左-右"，所以先將右子節(jié)點入棧，再將左子節(jié)點入棧。?時間復雜度O(n)?，空間復雜度O(n)。
14. 字符串轉換整數 (atoi) (String to Integer (atoi))
?問題描述?：實現字符串到整數的轉換。
?Java解答?：
public int myAtoi(String s) {
if (s == null || s.length() == 0) return 0;
int index = 0, sign = 1, total = 0;
// 跳過空格
while (index < s.length() && s.charAt(index) == ' ') index++;
if (index == s.length()) return 0;
// 處理符號
if (s.charAt(index) == '+' || s.charAt(index) == '-') {
sign = s.charAt(index) == '+' ? 1 : -1;
index++;
}
while (index < s.length()) {
int digit = s.charAt(index) - '0';
if (digit < 0 || digit > 9) break;
// 檢查溢出
if (Integer.MAX_VALUE / 10 < total ||
(Integer.MAX_VALUE / 10 == total && Integer.MAX_VALUE % 10 < digit)) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
total = total * 10 + digit;
index++;
}
return total * sign;
}?解析?：處理空格、正負號和數字字符。?關鍵處理整數溢出，檢查當前結果是否超過32位整數范圍。?時間復雜度O(n)?，空間復雜度O(1)。
15. 刪除鏈表的倒數第N個節(jié)點 (Remove Nth Node From End of List)
?問題描述?：刪除鏈表的倒數第n個節(jié)點。
?Java解答?：
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
for (int i = 0; i <= n; i++) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}?解析?：使用雙指針技術。第一個指針先移動n+1步，然后兩個指針同時移動，當第一個指針到達末尾時，第二個指針指向待刪除節(jié)點的前一個節(jié)點。?時間復雜度O(n)?，空間復雜度O(1)。
16. 括號生成 (Generate Parentheses)
?問題描述?：數字n代表生成括號的對數，生成所有有效的括號組合。
?Java解答?：
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(result, "", 0, 0, n);
return result;
}
private void backtrack(List<String> result, String current, int open, int close, int max) {
if (current.length() == max * 2) {
result.add(current);
return;
}
if (open < max) {
backtrack(result, current + "(", open + 1, close, max);
}
if (close < open) {
backtrack(result, current + ")", open, close + 1, max);
}
}?解析?：使用回溯算法。跟蹤當前開括號和閉括號數量，只有開括號數小于n時可添加開括號，只有閉括號數小于開括號數時可添加閉括號。?時間復雜度O(4^n/√n)?，空間復雜度O(n)。
17. 實現strStr() (Implement strStr())
?問題描述?：返回字符串中第一個匹配項的下標，不存在返回-1。
?Java解答?：
public int strStr(String haystack, String needle) {
if (needle.isEmpty()) return 0;
for (int i = 0; i <= haystack.length() - needle.length(); i++) {
for (int j = 0; j < needle.length() && haystack.charAt(i + j) == needle.charAt(j); j++) {
if (j == needle.length() - 1) return i;
}
}
return -1;
}?解析?：?暴力匹配，遍歷原字符串，對于每個位置，檢查是否與模式串匹配。也可使用KMP等高效算法。?平均時間復雜度O(n+m)?，最壞O(n×m)。
18. 搜索旋轉排序數組 (Search in Rotated Sorted Array)
?問題描述?：?旋轉過的升序數組中搜索目標值，返回索引。
?Java解答?：
public int search(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;
if (nums[left] <= nums[mid]) { // 左半部分有序
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // 右半部分有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}?解析?：?修改的二分查找。每次確定哪一半是有序的，并檢查目標是否在有序部分內。?時間復雜度O(log n)?，空間復雜度O(1)。
19. 在排序數組中查找元素的第一個和最后一個位置 (Find First and Last Position of Element in Sorted Array)
?問題描述?：給定排序數組和目標值，找出目標值開始和結束位置。
?Java解答?：
public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1};
result[0] = findBound(nums, target, true);
if (result[0] != -1) {
result[1] = findBound(nums, target, false);
}
return result;
}
private int findBound(int[] nums, int target, boolean isFirst) {
int left = 0, right = nums.length - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
index = mid;
if (isFirst) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return index;
}?解析?：使用兩次二分查找，第一次找起始位置，第二次找結束位置。找到目標后繼續(xù)向相應方向搜索。?時間復雜度O(log n)?，空間復雜度O(1)。
20. 組合總和 (Combination Sum)
?問題描述?：找出數組中所有可以使數字和為target的唯一組合。
?Java解答?：
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
backtrack(result, new ArrayList<>(), candidates, target, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> temp,
int[] candidates, int remain, int start) {
if (remain < 0) return;
if (remain == 0) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < candidates.length; i++) {
temp.add(candidates[i]);
backtrack(result, temp, candidates, remain - candidates[i], i);
temp.remove(temp.size() - 1);
}
}?解析?：使用回溯算法。對數組排序后，遞歸嘗試每個候選數，減少目標值，允許重復使用同一元素。?時間復雜度O(N^target)?，空間復雜度O(target)。
21. 全排列 (Permutations)
?問題描述?：給定沒有重復數字的序列，返回其所有可能排列。
?Java解答?：
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> temp,
int[] nums, boolean[] used) {
if (temp.size() == nums.length) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
temp.add(nums[i]);
backtrack(result, temp, nums, used);
temp.remove(temp.size() - 1);
used[i] = false;
}
}?解析?：使用回溯算法與used數組標記已使用元素。當臨時列表大小等于原數組時，找到一個排列。?時間復雜度O(n!)?，空間復雜度O(n)。
22. 合并兩個有序數組 (Merge Sorted Array)
?問題描述?：將兩個有序數組合并到第一個數組中。
?Java解答?：
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1, p = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p--] = nums1[p1--];
} else {
nums1[p--] = nums2[p2--];
}
}
System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}?解析?：使用三指針，從后向前處理。比較兩數組元素，較大者放入nums1末尾。?時間復雜度O(m+n)?，空間復雜度O(1)。
23. 驗證二叉搜索樹 (Validate Binary Search Tree)
?問題描述?：判斷二叉樹是否是有效的二叉搜索樹。
?Java解答?：
public boolean isValidBST(TreeNode root) {
return validate(root, null, null);
}
private boolean validate(TreeNode node, Integer low, Integer high) {
if (node == null) return true;
if ((low != null && node.val <= low) || (high != null && node.val >= high)) {
return false;
}
return validate(node.left, low, node.val) && validate(node.right, node.val, high);
}?解析?：使用遞歸，傳遞上下界。左子樹所有節(jié)點值應小于當前節(jié)點值，右子樹所有節(jié)點值應大于當前節(jié)點值。?時間復雜度O(n)?，空間復雜度O(n)。
24. 對稱二叉樹 (Symmetric Tree)
?問題描述?：檢查二叉樹是否是鏡像對稱的。
?Java解答?：
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val) &&
isMirror(t1.left, t2.right) &&
isMirror(t1.right, t2.left);
}?解析?：使用遞歸比較左右子樹。兩樹對稱當且僅當根節(jié)點值相等，且左子樹與右子樹鏡像對稱。?時間復雜度O(n)?，空間復雜度O(n)。
25. 二叉樹的中序遍歷 (Binary Tree Inorder Traversal)
?問題描述?：返回二叉樹中序遍歷的節(jié)點值。
?Java解答?：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
result.add(curr.val);
curr = curr.right;
}
return result;
}?解析?：使用棧模擬遞歸過程。中序遍歷順序為"左-根-右"，先遍歷左子樹到底，處理節(jié)點，再處理右子樹。?時間復雜度O(n)?，空間復雜度O(n)。
26. 最長公共前綴 (Longest Common Prefix)
?問題描述?：查找字符串數組中的最長公共前綴。
?Java解答?：
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
}
return prefix;
}?解析?：以第一個字符串作為初始前綴，依次與后續(xù)字符串比較，不斷縮短前綴直到匹配。?時間復雜度O(S)??（S為所有字符數），空間復雜度O(1)。
27. K個一組翻轉鏈表 (Reverse Nodes in k-Group)
?問題描述?：每k個節(jié)點一組進行翻轉，返回修改后的鏈表。
?Java解答?：
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (head != null) {
ListNode start = head;
ListNode end = prev;
for (int i = 0; i < k; i++) {
end = end.next;
if (end == null) return dummy.next;
}
ListNode next = end.next;
end.next = null;
prev.next = reverse(start);
start.next = next;
prev = start;
head = next;
}
return dummy.next;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}?解析?：使用虛擬頭節(jié)點簡化操作。找到每k個節(jié)點的起始和結束位置，翻轉該段子鏈表，再與前后部分連接。?時間復雜度O(n)?，空間復雜度O(1)。
28. 刪除排序數組中的重復項 (Remove Duplicates from Sorted Array)
?問題描述?：?原地刪除排序數組中的重復項，返回新長度。
?Java解答?：
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}?解析?：使用雙指針技術。慢指針i跟蹤唯一元素位置，快指針j遍歷數組。當發(fā)現不同元素時，移動慢指針并更新值。?時間復雜度O(n)?，空間復雜度O(1)。
29. 盛最多水的容器 (Container With Most Water)
?問題描述?：找出兩條線，使得它們與x軸共同構成的容器可以容納最多的水。
?Java解答?：
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
int area = Math.min(height[left], height[right]) * (right - left);
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}?解析?：使用雙指針從兩端向中間移動。容量由較矮的線和寬度決定。每次移動較矮一側的指針，因為移動較高側的指針不會增加容量。?時間復雜度O(n)?，空間復雜度O(1)。
30. 尋找兩個正序數組的中位數 (Median of Two Sorted Arrays)
?問題描述?：找出兩個正序數組的中位數，要求時間復雜度為O(log (m+n))。
?Java解答?：
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int x = nums1.length, y = nums2.length;
int low = 0, high = x;
while (low <= high) {
int partitionX = (low + high) / 2;
int partitionY = (x + y + 1) / 2 - partitionX;
int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
int minX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
int minY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
if (maxX <= minY && maxY <= minX) {
if ((x + y) % 2 == 0) {
return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2.0;
} else {
return Math.max(maxX, maxY);
}
} else if (maxX > minY) {
high = partitionX - 1;
} else {
low = partitionX + 1;
}
}
throw new IllegalArgumentException();
}?解析?：使用二分查找。對較短數組進行分割，確保左半部分全部小于右半部分。找到正確分割后，根據總數奇偶性計算中位數。?時間復雜度O(log(min(m,n)))?，空間復雜度O(1)。
總結
不同數據規(guī)模下的復雜度選擇建議
根據問題規(guī)模，可以參考以下選擇標準：
數據規(guī)模 (n) | 可接受的復雜度 | 推薦算法示例 |
|---|---|---|
n ≤ 100 | O(n³), O(n²) | 冒泡排序、簡單動態(tài)規(guī)劃 |
n ≤ 1,000 | O(n²), O(n log n) | 快速排序、簡單圖算法 |
n ≤ 100,000 | O(n log n) | 歸并排序、堆排序 |
n ≤ 1,000,000 | O(n), O(n log n) | 計數排序、并查集 |
n > 1,000,000 | O(log n), O(1) | 二分查找、哈希查找 |
實際應用中的操作次數對比（假設n=1000）
復雜度 | 操作次數（近似） | 實際應用場景 | 效率評價 |
|---|---|---|---|
O(1) | 1 | 哈希表訪問、數組索引 | 最優(yōu)，與輸入規(guī)模無關 |
O(log n) | ~10 | 二分查找、平衡樹操作 | 極高效，增速最慢 |
O(n) | 1000 | 遍歷數組/鏈表 | 高效，線性增長 |
O(n log n) | ~10,000 | 快速排序、歸并排序 | 較高效，適用于大數據 |
O(n²) | 1,000,000 | 冒泡排序、簡單矩陣乘法 | 低效，小規(guī)模數據可用 |
O(n³) | 1,000,000,000 | 三重循環(huán)（如暴力算法） | 非常低效，避免大規(guī)模 |
O(2?) | ~10³?¹ | 子集生成、窮舉組合 | 不可行，指數爆炸 |
O(n!) | ~10²??? | 全排列生成、旅行商問題（暴力） | 完全不可行 |
時間與空間復雜度的權衡
在實際算法設計中，經常需要在時間復雜度和空間復雜度之間進行權衡：
?以空間換時間?：使用額外的存儲空間來降低時間復雜度
?示例?：哈希表加速查找（從O(n)到O(1)）
?示例?：動態(tài)規(guī)劃中的記憶化存儲
?以時間換空間?：減少空間使用，但可能增加時間復雜度
?示例?：原地排序算法（如堆排序）
?示例?：流式處理大數據集
?固定空間算法?：無論輸入規(guī)模如何，使用恒定空間
?示例?：迭代算法代替遞歸算法減少?？臻g使用
如何分析算法復雜度
?時間復雜度分析?：
找出基本操作（最頻繁執(zhí)行的操作）
計算基本操作執(zhí)行次數與輸入規(guī)模n的關系
使用大O表示法表示最高階項，忽略常數因子和低階項
?空間復雜度分析?：
統計算法運行過程中動態(tài)分配的額外存儲空間
包括變量、數據結構、遞歸調用棧等
同樣使用大O表示法表示
?考慮最壞情況?：復雜度分析通常關注最壞情況下的性能，這提供了算法性能的保證上限。
掌握這些經典算法題不僅能幫助你在技術面試中脫穎而出，更能提升你解決實際問題的能力。建議反復練習，理解每種算法背后的思想，而不僅僅是記住代碼。編程之路漫漫，算法與數據結構是基石，祝你越走越遠！
總結
到此這篇關于30個最常見算法題及其Java實現和詳細解析的文章就介紹到這了,更多相關常見算法題Java實現內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了mybatis xml如何使用not in 某個集合的格式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-01-01
Java中的Web MVC簡介_動力節(jié)點Java學院整理
MVC模型是一種架構型的模式，本身不引入新功能，只是幫助我們將開發(fā)的結構組織的更加合理，使展示與模型分離、流程控制邏輯、業(yè)務邏輯調用與展示邏輯分離2017-09-09
這篇文章主要介紹了SpringBoot @NotBlank錯誤的解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
這篇文章主要介紹了Java利用策略模式優(yōu)化過多if else代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-09-09
這篇文章主要介紹了Java中實現多線程關鍵詞整理，非常不錯，具有參考借鑒價值,需要的朋友可以參考下2017-05-05
這篇文章主要為大家介紹了Jenkins忘記密碼密碼重置操作步驟詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09
定時任務一般是項目中都需要用到的，可以用于定時處理一些特殊的任務。下面這篇文章主要給大家介紹了關于Spring Boot中實現定時任務應用實踐的相關資料，文中通過示例代碼介紹的非常詳細，需要的朋友可以參考下。2018-05-05
這篇文章主要介紹了Java設計模式之策略模式（Strategy模式）介紹,Strategy是屬于設計模式中對象行為型模式,要是定義一系列的算法,這些算法一個個封裝成單獨的類,需要的朋友可以參考下2015-03-03
Linux將Spring Boot項目的Jar包注冊為開機自啟動系統服務的操作方法
jar文件是從maven package打包出來的,config/application.yml是原先在項目的resources文件夾里,外置出來方便適配開發(fā)環(huán)境和正式環(huán)境,這篇文章主要介紹了Linux將Spring Boot項目的Jar包注冊為開機自啟動系統服務的操作方法,需要的朋友可以參考下2023-10-10
這篇文章主要為大家介紹了ShardingSphere解析SQL的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08