例题：
31.下一个排列
思路：
因为我们要找到的下一个排列是大于该排列的最小的排列，所以我们可以从后往前扫描第一个正序的元素，然后将该元素与其后面的元素比较大小，找到比它大的元素中最小的元素，然后交换这两个元素，最后将后面的元素逆转即可（逆转就是按照升序排列，因为第一遍扫描的时候会扫描国的元素是按照降序排列的），步骤如下：
1.从数组的末尾开始，寻找第一个正序的数字，通过找到第一个满足nums[k-1] < nums[k]的索引k来判断。
2.如果找不到这样的数字，说明整个数组是降序排列的，即没有下一个更大的排列。此时将整个数组翻转，得到最小的排列。
3.如果找到了正序的数字，继续从末尾向前扫描，找到第一个大于nums[k-1]的数字，记为nums[t]。
4.交换nums[k-1]和nums[t]两个元素，将较大的数字放到前面。
5.将索引k之后的元素进行翻转操作，使得这部分元素成为升序排列，从而得到下一个排列。视频讲解点击视频讲解-下一个排列。
时间复杂度：
时间复杂度为O(n)，其中n是nums数组的长度。
代码实现：
class Solution {
public void nextPermutation(int[] nums) {
//从后向前寻找第一个正序的数字
int k = nums.length - 1;
while(k > 0 && nums[k-1] >= nums[k]) k--;
if(k <= 0){
//直接翻转数组
int i = 0;
int j = nums.length - 1;
reserve(nums,i,j);
}else{
//从后向前扫描，找到第一个大于nums[k-1]的值
int t = nums.length - 1;
while( nums[t] <= nums[k-1]) t--;
//交换两个元素
int temp2 = nums[k-1];
nums[k-1] = nums[t];
nums[t] = temp2;
//翻转剩余的后面的元素
int start = k;
int end = nums.length - 1;
reserve(nums,start,end);
}
}
private void reserve(int arr[],int start,int end){
while(start < end){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
}
75.颜色分类
思路：
本题采用三指针解决，使用三个指针i、j、k来分别表示红色、白色、蓝色的分界位置，通过while循环遍历数组，当j指向的元素为0时，与i位置的元素进行交换，同时将i和j都向后移动一位。当j指向的元素为2时，与k位置的元素进行交换，同时将k向前移动一位。如果j指向的元素为1，则仅将j向后移动一位。这样遍历一次数组后，就可以将数组中的0全部移动到前面，将2全部移动到后面，1的位置则自然被安排在中间。
这里说明一下为什么j指向0时交换后需要后移而指向2时交换不用后移，原因在于i，j是同时从索引0处出发的，在j指向的值为2时，与k指向的值交换，此时k之前指向的值是多少我们是不知道的，可能交换后j指向的新值还需要进行交换，所以此时j指针是不用动的，k指针后移；i指针和j指针刚开始是同步的（指向0和2的时候i，j要么都移动，要么都不移动），只有在指向1的时候j指针后移，i指针不动，所以可以得出j指针和i指针要么同步，要么j指针会在i指针的后面，所以i指针不会指向2（除了索引0处的值是2的情况下），只会指向0和1，且i指针前面的数全部都是0，如果还是不太理解这一点，可以自己多模拟几个例子，视频讲解点击视频讲解-颜色分类。
时间复杂度：
时间复杂度为O(n)，其中n为数组nums的长度。
代码实现：
class Solution {
public void sortColors(int[] nums) {
int i = 0;
int j = 0;
int k =nums.length - 1;
while(j <= k){
if(nums[j] == 0){
swapnum(nums,i,j);
i++;
j++;
}
else if(nums[j] == 2) {
swapnum(nums,j,k);
k--;
}
else j++;
}
}
//注意：这里不能简单的交换两个数（即swap(int a,int b)），因为交换的只是形参的值，并不会影响到原始数组nums中的值
//所以应该修改为交换数组中指定位置的值，而不是交换形参的值
private void swapnum(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
88.合并两个有序数组
思路：
本题采用双指针来解决，用两个指针分别遍历两个数组，依次比较数组元素的大小，需要注意的是，本题需要在nums1的基础上进行改变，不能使用额外的空间，如果正序遍历会将nums1中的某些元素覆盖掉，所以我们采用逆序遍历，将两数组中的元素从大到小依次加入到nums1中即可，视频讲解点击视频讲解-合并两个有序数组。
时间复杂度：
时间复杂度为O(m+n)，在最坏情况下，我们需要遍历nums1数组的m次和nums2数组的n次。
代码实现：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int idx = m + n - 1;
int i = m - 1;
int j = n - 1;
while(i >= 0 && j >= 0){
if(nums1[i] >= nums2[j]) nums1[idx--] = nums1[i--];
else nums1[idx--] = nums2[j--];
}
while(j >= 0) nums1[idx--] = nums2[j--];
}
}
215.数组中的第k个最大元素
思路：
本题采用优先队列来求解，由于要求解数组中的第k个最大元素，首先，遍历数组中的每个元素，如果队列的大小小于k，则直接将元素插入队列中；如果队列的大小已经达到k，那么比较当前元素与队列中最小的元素的大小，如果当前元素大于最小元素，则删除最小元素，并将当前元素插入队列。最后，队列中的最小元素即为第k大的元素，返回即可。
时间复杂度：
时间复杂度为O(nlogk)，其中n为数组长度。在最坏情况下，需要遍历数组中的每个元素，每次插入操作都需要调整堆的结构，而调整堆的时间复杂度为O(logk)。
代码实现：
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for(int num : nums){
if(heap.size() < k){
heap.add(num);
}else if(heap.peek() < num) {
heap.poll();
heap.add(num);
}
}
return heap.poll();
}
}
知识拓展：
java中堆的用法：
在Java中，堆通常指的是PriorityQueue，它是一个基于优先级堆的无界队列。以下是一些常用API及其使用示例：
//1.创建一个空的优先队列
PriorityQueue<Integer> queue = new PriorityQueue<>();
//将元素添加到队列中
queue.offer(10);
//获取并移除队列的最小元素（最小元素是指优先级最高的元素，这取决于队列是最小堆还是最大堆）
queue.poll();
//获取但不移除队列的最小元素
queue.peek();
//获取队列中元素的数量
queue.size();
//检查队列是否为空
queue.isEmpty();
这些是PriorityQueue的基本API，它们提供了基本的堆操作。PriorityQueue不是同步的，需要手动实现同步机制，或者使用PriorityBlockingQueue，它是同步的。
283.移动零
思路：
本题使用一个指针idx来指示当前非零元素应该放置的位置。遍历整个数组，如果当前元素不为0，则将其放置在idx位置，然后将idx加1，这样，遍历完整个数组后，所有非零元素都被放置在了数组的前部。接着，我们需要将剩余的位置都填上0，以满足将所有0元素移动到末尾的要求，通过一个while循环，不断将idx位置及之后的元素赋值为0，直到数组的末尾。
时间复杂度：
时间复杂度为O(n)，其中n为数组nums的长度。
代码实现：
class Solution {
public void moveZeroes(int[] nums) {
int idx = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] != 0){
nums[idx++] = nums[i];
}
}
while(idx < nums.length){
nums[idx++] = 0;
}
}
}
287.寻找重复数
思路1：
使用Set来解决，因为Set有一个特性是其中的元素必须不能重复，如果往Set中添加重复元素，那么set.add(x)将返回false，使用一个 HashSet 来存储已经遍历过的数字，当遍历到一个数字时，如果该数字已经存在于 HashSet 中，则说明该数字是重复的，将其赋值给变量 ans。
时间复杂度：
时间复杂度为 O(n)，其中 n 是数组的长度。
代码实现：
class Solution {
public int findDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
int ans = 0;
for(int num : nums){
if(!set.add(num)){
ans = num;
}
}
return ans;
}
}
思路2：
使用哈希表来解决，以数组元素为键值，记录每个值出现的次数，遍历数组，使用map.containsKey(x)函数来判断数组元素是否存在于哈希表中，如果存在，则返回该元素，否则将该元素加入哈希表，继续遍历直到找到符合条件的数组元素。
时间复杂度：
时间复杂度为 O(n)，其中 n 是数组的长度。
代码实现：
class Solution {
public int findDuplicate(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
if(nums.length == 0) return 0;
else{
for(int num : nums){
if(map.containsKey(num)){
return num;
}else{
map.put(num,1);
}
}
}
return 0;
}
}
思路3：
使用快慢指针来解决，快指针每次移动两步，慢指针每次移动一步，直到它们相遇，说明存在环。接下来，将快指针重新指向数组的起始位置，然后快慢指针分别以一步的速度移动，直到它们再次相遇，此时的相遇点就是重复的数。证明过程可以点击观看快慢指针证明，这是我找到的讲的最详细的博主，类似的题目142.环形链表Ⅱ。
时间复杂度：
该算法的时间复杂度为O(n)，其中n是数组的长度。
代码实现：
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]];
}
fast = 0;
while(slow != fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
300.最长递增子序列
思路：
本题采用动态规划解决，使用dp[i]来表示以第i个元素为结尾的最长递增子序列，dp[j]表示以在dp[j]之前的某个元素结尾的最长递增子序列，那么可以得到动态规划方程，当nums[i] > nums[j]时，dp[i] = max(dp[i],dp[j] + 1)（使用max是因为第i个元素之前有很多个元素，每个比nums[i]小的元素都可以得到一个dp[i]，我们需要求最大值），最后将得到的每个最大的dp[i]取最大值即可得到最长递增子序列。
时间复杂度：
时间复杂度为O(n^2)，其中n是数组的长度。
代码实现：
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp,1);
int ans = 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);
}
}
ans = Math.max(ans,dp[i]);
}
return ans;
}
}
347.前K个高频元素
思路：
本题首先采用哈希表存储每个元素出现的次数，以数组元素为key，以其出现的次数为value，在得到哈希表后创建一个优先队列（小根堆），存储频率最高的前k个元素，然后将存储的元素移到结果数组中，最后返回数组即可。
时间复杂度：
时间复杂度为O(n log k)，其中n是数组nums的长度。
- 创建
map并遍历整个数组：时间复杂度为O(n)。 - 将频率最高的
k个元素存入优先队列（最小堆）：最坏情况下，插入一个元素到优先队列的时间复杂度为O(logk)，因此插入k个元素的时间复杂度为O(k log k)。 - 将优先队列中的元素移入数组：最坏情况下，移除堆顶元素的时间复杂度为
O(log k)，因此移除k个元素的时间复杂度为O(klog k)。
代码实现：
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//创建map来记录每个数组元素出现的次数
Map<Integer,Integer> map = new HashMap<>();
//遍历数组,以数组元素作为key,出现的次数作为value
//map.getOrDefault(num , 0) + 1是从一个Map（映射）中获取与指定的"num"键关联的值
//如果该键不存在,则返回默认值0,然后将获取的值加1,并将结果存回Map中;
//如果指定的键存在于Map中,那么这行代码会返回该键对应的值,并将其加1
for(int num : nums){
map.put(num , map.getOrDefault(num , 0) + 1);
}
//使用优先队列(最小堆)来存储频率最高的k个元素
//PriorityQueue<Map.Entry<Integer,Integer>>表示这个优先队列的元素类型是Map.Entry<Integer, Integer>
//Comparator.comparingInt(Map.Entry::getValue)为优先队列指定了一个比较器Comparator。这个比较器使用键值对的值（即频率）进行比较，以便在优先队列中按照频率的升序进行排列
//Comparator.comparingInt()方法，传入一个Lambda表达式来提取Entry的值进行比较,Map.Entry::getValue表示使用Entry的getValue()方法作为比较的依据。这种写法可以用于对Map中的Entry按值进行排序操作
PriorityQueue<Map.Entry<Integer,Integer>> minHeap = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
//遍历频率映射,map.entrySet()返回的是一个包含Map中所有键值对的Set集合，每个元素都是一个Map.Entry对象，表示一个键值对,每个Map.Entry对象中保存着键和对应的值
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
minHeap.offer(entry);
//如果minHeap的大小超过k,则移除堆顶元素
if(minHeap.size() > k){
minHeap.poll();
}
}
//通过上面的处理堆中存储的就是前k个高频元素,将堆中的元素移到数组中
int[] ans = new int[k];
int idx = 0;
while(!minHeap.isEmpty()){
//minHeap.poll.getKey(),由于获得的是一个map的键值对,需要拿到key的值,即数组的元素
ans[idx++] = minHeap.poll().getKey();
}
return ans;
}
}
方法总结
1.指针（三指针，双指针，快慢指针）（75、88、283、287）
2.哈希表（287、347）
哈希表一般用来记录数组中各元素出现的次数，以求得出现次数最多或最少的元素。
3.优先队列（堆）（215、347）
优先队列是一种特殊的队列，其中的元素按照一定的优先级进行排序。堆是一种经典的优先队列实现方式，通过维护一个二叉堆来实现优先队列的操作。堆适用于需要快速找到最大或最小元素的场景，常见的操作包括插入元素和删除最大（最小）元素，其时间复杂度为O(logN)。
4.动态规划（300）
通过将问题拆分为更小的子问题，并保存子问题的解决结果，最终得到问题的最优解。动态规划适用于具有重叠子问题和最优子结构性质的问题，常见的操作包括状态定义、状态转移方程的定义和最优解的计算。