刷题训练条记

目次
1、消散的数字
2、旋转数组
3、原地移除元素
4、删除排序数组中的重复项

---

1、消散的数字

oj：口试题 17.04. 消散的数字 - 力扣（LeetCode）

   思绪（参考品评区）：
  利用异或的特性，ret = ret ^ x ^ x。级对同一个值异或两次，效果即是它自己
  以是对 ret 从 0 - nums.length 举行异或，同时对 nums 数组中的值举行异或，出现重复的会消散，以是末了 ret 的值是只出现一次的数字，也就是nums数组中缺失的谁人数字。

1. class Solution {
2.     public int missingNumber(int[] nums) {
3.         int ret = 0;
4.         for(int i = 0; i < nums.length; i++) {
5.             ret ^= i;
6.             ret ^= nums[i];
7.         }
8.         ret ^= nums.length;
9.         return ret;
10.     }
11. }

复制代码

2、旋转数组

oj：189. 轮转数组 - 力扣（LeetCode）

   思绪：
  1. 利用额外的数组将每个元素放至旋转后的位置
  2. 遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k)%n 的位置
  3. 再把新数组写回原数组

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

复制代码

3、原地移除元素

oj：226. 翻转二叉树 - 力扣（LeetCode）

   思绪：
  1. 遍历数组 nums，设置一个下标 ans
2. 在遍历过程中如果出现数字不是须要被移除的值，则把这个数字覆盖到ans地点的下标位置，ans 自增 1
3. 如果雷同的时间，则跳过该数字不举行覆盖，末了 ans 即为新的数组长度

1. // 时间复杂度：O(n)，空间复杂度：O(1)
2. class Solution {
3.     public int removeElement(int[] nums, int val) {
4.         int ans = 0;
5.         for(int i = 0; i<nums.length; i++) {
6.             if(nums[i] != val) {
7.                 nums[ans] = nums[i];
8.                 ans++;
9.             }
10.         }
11.         return ans;
12.     }
13. }

复制代码

4、删除排序数组中的重复项

oj：26. 删除有序数组中的重复项 - 力扣（LeetCode）

   思绪：
  1. 与上题类似，利用两个指针，fast用于遍历数组，slow位置用于存放不重复项
  2. 在遍历过程中如果出现数字不是重复值，则把这个数字覆盖到slow地点的下标位置
  3. slow+1 即为数组中唯一元素的数量 

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

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。