1.删除排序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

双指针解决

使用两个指针，右指针始终往右移动，
如果右指针指向的值等于左指针指向的值，左指针不动。
如果右指针指向的值不等于左指针指向的值，那么左指针往右移一步，然后再把右指针指向的值赋给左指针。

解法①√

  1.     //双指针解决
  2.     public int removeDuplicates(int[] A) {
  3.         //边界条件判断
  4.         if (A == null || A.length == 0)
  5.             return 0;
  6.         int left = 0;
  7.         for (int right = 1; right < A.length; right++)
  8.             //如果左指针和右指针指向的值一样，说明有重复的，
  9.             //这个时候，左指针不动，右指针继续往右移。如果他俩
  10.             //指向的值不一样就把右指针指向的值往前挪
  11.             if (A[left] != A[right])
  12.                 A[++left] = A[right];
  13.         return ++left;
  14.     }

解法②

  1.     public int removeDuplicates(int[] A) {
  2.         int count = 0;//重复的数字个数
  3.         for (int right = 1; right < A.length; right++) {
  4.             if (A[right] == A[right - 1]) {
  5.                 //如果有重复的，count要加1
  6.                 count++;
  7.             } else {
  8.                 //如果没有重复，后面的就往前挪
  9.                 A[right - count] = A[right];
  10.             }
  11.         }
  12.         //数组的长度减去重复的个数
  13.         return A.length - count;
  14.     }

算法演示：

  1. int[] ints = {1,2,2,2,3,4,4,5,5,5,5};
  2. A[1]!=A[0] A[1]=A[1] count=0
  3. A[2]==A[1] count=1;
  4. A[3]==A[2] count=2;
  5. A[4]!=A[3] A[4-2]=A[4] => int[] ints = {1,2,3,2,3,4,4,5,5,5,5};
  6. A[5]!=A[4] A[5-2]=A[5] => int[] ints = {1,2,3,4,3,4,4,5,5,5,5};
  7. A[6]==A[5] count=3;
  8. A[7]!=A[6] A[7-3]=A[7] => int[] ints = {1,2,3,4,5,4,4,5,5,5,5};
  9. ......

解法③

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         int i = 0;
  5.         for (int j = 1; j < nums.length; j++) {
  6.             if (nums[i] != nums[j]) {
  7.                 i++;
  8.                 nums[i] = nums[j];
  9.             }
  10.         }
  11.         return i + 1;
  12.     }
  13. }

2.旋转数组

解法1 使用临时数组√

可以使用一个临时数组，先把原数组的值存放到一个临时数组中，然后再把临时数组的值重新赋给原数组，重新赋值的时候要保证每个元素都要往后移k位，如果超过数组的长度就从头开始，所以这里可以使用(i + k) % length来计算重新赋值的元素下标

  1. //旋转数组
  2.     public void rotate(int nums[], int k) {
  3.         int length = nums.length;
  4.         int temp[] = new int[length];
  5.         //把原数组值放到一个临时数组中，
  6.         for (int i = 0; i < length; i++) {
  7.             temp[i] = nums[i];
  8.         }
  9.         //然后在把临时数组的值重新放到原数组，并且往右移动k位
  10.         for (int i = 0; i < length; i++) {
  11.             nums[(i + k) % length] = temp[i];
  12.         }
  13.     }

解法2 多次反转

先反转全部数组，在反转前k个，最后在反转剩余的，如下所示
image.png

  1. class Solution {
  2.     public void rotate(int[] nums, int k) {
  3.         int length = nums.length;
  4.         k%=length;
  5.         reverse(nums,0,length-1);
  6.         reverse(nums,0,k-1);
  7.         reverse(nums,k,length-1);
  8.     }
  9.     void reverse(int []nums,int start,int end){
  10.         while(start<end){
  11.             int temp = nums[start];
  12.             nums[start]=nums[end];
  13.             nums[end]=temp;
  14.             start++;
  15.             end--;
  16.         }
  17.     }
  18. }

解法3

使用长度为k的数组temp存放数组后面k个数，
将前面nums.length - k个数从最右边开始依次向右移动k位，
把temp保存的数插入到数组前面

  1. public void rotate(int[] nums, int k) {
  2.         k = k % nums.length;
  3.         int temp[] = new int[k];
  4.         int j = 0;
  5.         for (int i = nums.length - k; i < nums.length; i++) {
  6.             temp[j++] = nums[i];
  7.         }
  8.         for (int i = nums.length - k - 1; i >= 0; i--) {
  9.             nums[i + k] = nums[i];
  10.         }
  11.         for (int i = 0; i < temp.length; i++) {
  12.             nums[i] = temp[i];
  13.         }
  14.     }