Task14：完成以下三个题目并打卡（1天）
215 数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
partition（切分）操作，使得：
- 对于某个索引 j，nums[j] 已经排定，即 nums[j] 经过 partition（切分）操作以后会放置在它 “最终应该放置的地方”；
- nums[left] 到 nums[j - 1] 中的所有元素都不大于 nums[j]；
- nums[j + 1] 到 nums[right] 中的所有元素都不小于 nums[j]。
import java.util.Random;
public class Solution {
private static Random random = new Random(System.currentTimeMillis());
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
int target = len - k;
int left = 0;
int right = len - 1;
while (true) {
int index = partition(nums, left, right);
if (index < target) {
left = index + 1;
} else if (index > target) {
right = index - 1;
} else {
return nums[index];
}
}
}
// 在区间 [left, right] 这个区间执行 partition 操作
private int partition(int[] nums, int left, int right) {
// 在区间随机选择一个元素作为标定点
if (right > left) {
int randomIndex = left + 1 + random.nextInt(right - left);
swap(nums, left, randomIndex);
}
int pivot = nums[left];
int j = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] < pivot) {
j++;
swap(nums, j, i);
}
}
swap(nums, left, j);
return j;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
217 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
Java 用 stream 实现一行将 int[] 转成 Set
class Solution {
public boolean containsDuplicate(int[] nums) {
return IntStream.of(nums).distinct().count() != nums.length;
}
}
遍历数组，数字放到 set 中。如果数字已经存在于 set 中，直接返回 true。如果成功遍历完数组，则表示没有重复元素，返回 false。
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num: nums) {
if (set.contains(num)) {
return true;
}
set.add(num);
}
return false;
}
}
230 二叉搜索树中第K小的元素
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3
进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
参考剑指offer的面试题54
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int k, ans;
// Recursive Solution
public int kthSmallest(TreeNode root, int k) {
this.k = k;
inOrder(root);
return ans;
}
private boolean inOrder(TreeNode root) {
if (null == root) return false;
if (inOrder(root.left)) return true;
if (--k == 0) {
ans = root.val;
return true;
}
return inOrder(root.right);
}
// Iterative Solution
public int kthSmallestII(TreeNode root, int k) {
Deque<TreeNode> stk = new ArrayDeque<>();
TreeNode p = root;
while (!stk.isEmpty() || null != p) {
while (null != p) {
stk.push(p);
p = p.left;
}
TreeNode cur = stk.pop();
if (--k == 0) return cur.val;
p = cur.right;
}
return -1; // unreachable statement
}
}