31. 下一个排列 – 力扣（LeetCode）
class Solution {
public void nextPermutation(int[] nums) {
//从右往左找到第一个num[i]<nums[i+1]的
int i = nums.length – 2;
while(i>=0 && nums[i]>=nums[i+1]){
i–;
}
//存在略大一些的排列
if(i>=0){
//从右往左找第一个比 nums[i]大的数
int j = nums.length – 1;
while(nums[j]<=nums[i]){
j–;
}
//交换nums[i]和nums[j]
swap(nums,i,j);
}
reverse(nums,i+1,nums.length-1);
}
private void swap(int[] nums,int left,int right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
private void reverse(int[] nums,int left,int right){
while(left<right){
swap(nums,left,right);
left++;
right–;
}
}
}
时间复杂度：O(N)
空间复杂度：O(1)
287. 寻找重复数 – 力扣（LeetCode）
快慢指针：
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[nums[0]];
//找相遇点（慢的走一格 快的走两格）
while(slow!=fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
//找环入口（慢的走一格 快的走一格）
slow = 0;
while(slow!=fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
时间复杂度：O(N)
空间复杂度：O(1)
295. 数据流的中位数 – 力扣（LeetCode）
大根堆 + 小根堆：
class MedianFinder {
PriorityQueue<Integer> small;
PriorityQueue<Integer> large;
public MedianFinder() {
small = new PriorityQueue<>((a,b) -> Integer.compare(b,a));
large = new PriorityQueue<>();
}
public void addNum(int num) {
//优先进 small
if(small.isEmpty() || num < small.peek()){
small.offer(num);
}
else{
large.offer(num);
}
//保证 large 的长度比 small 小
if(small.size() > large.size()+1){
large.offer(small.poll());
}
else if(large.size() > small.size()){
small.offer(large.poll());
}
}
public double findMedian() {
if(small.size() > large.size()){
return small.peek();
}
else{
return ((double)small.peek() + large.peek()) / 2.0;
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
