Java算法笔试题及答案
一、数组类题目：数组中的第K个最大元素
题目描述
给定一个未排序的整数数组nums和一个整数K，请找出数组中第K个最大的元素（注：这里的“第K大”指排序后从大到小的第K个，而非去重后的第K个）。
示例
输入：nums=[3,2,1,5,6,4]，K=2
输出：5（排序后数组为[6,5,4,3,2,1]，第2大元素是5）
解法思路
基础思路（排序法）：先对数组升序排序，再取倒数第K个元素（索引为nums.length-K），优点是代码简单，缺点是时间复杂度较高。
优化思路（小顶堆法）：维护一个大小为K的小顶堆，遍历数组时将元素加入堆，若堆大小超过K则弹出堆顶（当前堆中最小元素），遍历结束后堆顶即为第K大元素，时间复杂度更优。
代码实现（小顶堆法）
importjava.util.PriorityQueue;
publicclassFindKthLargest{
publicintfindKthLargest(int[]nums,intK){
//边界校验：处理空数组或K无效的情况
if(nums==null||nums.length==0||K1||Knums.length){
thrownewIllegalArgumentException(输入参数无效);
}
//Java的PriorityQueue默认是小顶堆，正好满足需求
PriorityQueueIntegerminHeap=newPriorityQueue(K);
for(intnum:nums){
minHeap.offer(num);
//当堆大小超过K时，弹出最小元素（保证堆中始终是当前最大的K个元素）
if(minHeap.size()K){
minHeap.poll();
}
}
//堆顶就是第K个最大元素（堆中最小的元素即第K大）
returnminHeap.peek();
}
//测试方法
publicstaticvoidmain(String[]args){
FindKthLargestsolution=newFindKthLargest();
int[]nums={3,2,1,5,6,4};
intK=2;
System.out.println(solution.findKthLargest(nums,K));//输出5
}
}
复杂度分析
时间复杂度：O(nlogK)，遍历数组耗时O(n)，堆的插入/弹出操作耗时O(logK)（堆大小始终为K）。
空间复杂度：O(K)，堆最多存储K个元素。
二、链表类题目：反转链表的指定区间
题目描述
给你单链表的头节点head，以及两个整数left和right（1≤left≤right≤链表长度），请反转从位置left到位置right的链表节点，返回反转后的链表头节点。
示例
输入：head=1-2-3-4-5，left=2，right=4
输出：1-4-3-2-5
解法思路
先找到反转区间的“前驱节点”（即第left-1个节点，若left=1则前驱为null）；
反转left到right之间的节点（类似普通链表反转，用prev、curr、next三个指针控制）；
将前驱节点连接到反转后的区间头，反转后的区间尾连接到原区间的后继节点（第right+1个节点）。
代码实现
classListNode{
intval;
ListNodenext;
ListNode(){}
ListNode(intval){this.val=val;}
ListNode(intval,ListNodenext){this.val=val;this.next=next;}
}
publicclassReverseBetween{
publicListNodereverseBetween(ListNodehe