1. 田忌赛马背后的算法

870. 优势洗牌

图片.png

和田忌赛马类似，这里你有多匹马（数组有多个元素） 将A中的最大元素记为A1, 次大元素记作A2….最小元素记作An 将B中的最大元素记为B1, 次大元素记作B2….最小元素记作Bn 如果A1>B1,那么就将A1放在B1的位置上，不用考虑如果A2>B1, 将A2和B1比，因为A2都比B1大了，那么A2肯定比B中所有的元素都大，不必吝啬A1 如果A1<B1，就拿A中目前没有使用过的最小元素来和B1比 因为要保持B中的元素顺序，而又要获得B中元素的降序序列，因此可以用一个优先级队列来保存B中元素以及对应下标

  1. class Solution {
  2.     public int[] advantageCount(int[] nums1, int[] nums2) {
  4.          int n=nums1.length;
  5.          //如果后面数组元素较大-->b[1]-a[1]>0-->交换--->最终降序
  6.          //q中记录的是nums2中的元素及其下标  并且按照元素值降序
  7.          //之所以保存下标 是因为后面nums1中的元素应该放在哪个位置和nums2中的元素位置有关
  8.          PriorityQueue<int[]> q=new PriorityQueue<>(
  9.              new Comparator<int[]>()
  10.              {
  11.                  public int compare(int[] a,int[] b)
  12.                  {
  13.                      return b[1]-a[1];
  14.                  }
  15.              }
  17.          );
  18.          //加入nums2中的元素
  19.          for(int i=0;i<n;i++)
  20.             q.offer(new int[]{i,nums2[i]});
  21.          Arrays.sort(nums1);
  22.          int[] ans=new int[n];
  23.          int left=0,right=n-1;
  24.          while(!q.isEmpty())
  25.          {
  26.              int[] temp=q.poll();
  27.              int i=temp[0],val=temp[1];
  28.              //当前nums1的“马”可以打败nums2的“马” 就直接用这匹马
  29.              if(nums1[right]>val)
  30.              {
  31.                  ans[i]=nums1[right];
  32.                  right--;
  33.              }
  34.             //当前nums1的“马”不可以打败nums2的“马” 就用nums1中最差的“马”（最小的元素）来匹配
  35.              else
  36.              {
  37.                  ans[i]=nums1[left];
  38.                  left++;
  39.              }
  40.          }
  41.          return ans;
  44.     }
  45. }
  46. //O(nlogn) 排序的复杂度
  47. //O(n)  优先级队列的空间消耗

2. 原地修改数组

26. 删除有序数组中的重复项

图片.png
图片.png

如果可以有额外空间的话，可以先用set去重，然后将set中的元素加入新的数组，并对新的数组进行排序即可 这里要求原地修改数组，一种最简单的做法是比较前后两个元素，如果相等则删除，这种找到一个元素就删除一次的时间复杂度是O(n^2) 思路：双指针 使用一个slow指针，fast指针，fast指针在前面探路，如果fast指向的元素和slow指向的元素不一样，则让slow往前走一步，并且slow走完之后的位置上面的值用fast指向的值更新

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         int slow=0,fast=1;
  4.         while(fast<nums.length)
  5.         {
  6.             if(nums[slow]!=nums[fast])
  7.             {
  8.                 slow++;
  9.                 nums[slow]=nums[fast];
  10.             }
  11.             fast++;
  12.         }
  13.         return slow+1;//数组的长度是索引加1
  14.     }
  15. }
  16. //O(n)
  17. //O(1)

类比这道数组去重，下面看一道链表去重的题目，题目解法类似

83. 删除排序链表中的重复元素

图片.png

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode deleteDuplicates(ListNode head) {
  13.         if(head==null)
  14.             return null;
  15.         //int slow=0,fast=1;
  16.         ListNode slow=head,fast=head.next;
  17.         while(fast!=null)
  18.         {
  19.             //if(nums[fast]!=nums[slow])
  20.             if(fast.val!=slow.val)
  21.             {
  22.                 slow=slow.next;//slow++
  23.                 slow.val=fast.val;//nums[slow]=nums[fast];
  24.             }
  25.             fast=fast.next;//fast++
  26.         }
  27.         slow.next=null;//断开与后面节点的连接
  28.         return head;
  30.     }
  31. }
  32. //O(n)
  33. //O(1)

27. 移除元素

图片.png

和前面的去重类似，但是去重之后的结果至少有1个元素，这里移除可能最后的结果没有元素剩余

  1. class Solution {
  2.     public int removeElement(int[] nums, int val) {
  3.         int slow=0,fast=0;//和去重不同 去重的话fast可以初始化为1 因为nums[0]==nums[0]没有意义
  4.         //这里由于nums[0]可能就是val 因此fast为0
  5.         while(fast<nums.length)
  6.         {
  7.             if(nums[fast]!=val)
  8.             {
  9.                 nums[slow]=nums[fast];
  10.                 slow++;//这里后++ 先++的话可能如果[1,2] 1这种情况 会将1保存下来
  11.             }
  12.             fast++;
  13.         }
  14.         return slow;//这里返回slow
  15.         //去重之后最小有1个元素保留  这里的移除可能没有元素保留 因此一个返回slow+1 一个返回slow
  17.     }
  18. }
  19. //O(n)
  20. //O(1)

283. 移动零

图片.png

这里的移动0相当于两步操作：

  1. 和前面一题相似，将数组中元素等于0的元素全部移除
  2. 在数组的末尾补上0
  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.         int n=nums.length;
  4.         int slow=0,fast=0;
  5.         int noZero=0;//记录非0的个数
  6.         while(fast<n)
  7.         {
  8.             if(nums[fast]!=0)//移除0
  9.             {
  10.                 nums[slow]=nums[fast];
  11.                 slow++;
  12.                 noZero++;
  13.             }
  14.             fast++;
  15.         }
  16.         for(int i=n-1,j=n-noZero;j>0;j--,i--)
  17.         {
  18.             nums[i]=0;//在数组末尾补上0
  19.         }
  21.     }
  22. }
  23. //O(n)
  24. //O(1)

这一题还有一种优化的解法，不需要在末尾额外添加0，直接通过交换一次性完成 交换的情形有两种

  1. 自己和自己交换
  2. left指向的0和fast指向的非0元素交换
  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.         int n=nums.length;
  4.         int slow=0,fast=0;
  5.         while(fast<n)
  6.         {
  7.             if(nums[fast]!=0)
  8.             {
  9.                 swap(nums,slow,fast);
  10.                 slow++;
  11.             }
  12.             fast++;
  14.         }
  16.     }
  17.     public void swap(int[] nums,int i,int j)
  18.     {
  19.         int x=nums[i];
  20.         nums[i]=nums[j];
  21.         nums[j]=x;
  22.     }
  23. }
  24. //O(n)
  25. //O(1)