双周赛113: 前3题

双周赛113：前3题

本次双周赛的前3题难度适中，比较适合自己的学习。由于接了实习，最近也同样在学习有关的开发知识，力扣刷得不多。现在开始刷题学习之旅吧~

​

T1. 使数组成为递增数组的最少右移次数

1.1 题目说明

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中的元素为 互不相同 的正整数。请你返回让 nums 成为递增数组的 最少右移 次数，如果无法得到递增数组，返回 -1 。

一次 右移 指的是同时对所有下标进行操作，将下标为 i 的元素移动到下标 (i + 1) % n 处。

示例 1：

输入：nums = [3,4,5,1,2]
输出：2
解释：
第一次右移后，nums = [2,3,4,5,1] 。
第二次右移后，nums = [1,2,3,4,5] 。
现在 nums 是递增数组了，所以答案为 2 。

示例 2：

输入：nums = [2,1,4]
输出：-1
解释：无法将数组变为递增数组。

提示：

• 1 <= nums.length <= 100

• 1 <= nums[i] <= 100

• nums 中的整数互不相同。

  ​

---

1.2 解答分析

• 读题之后可以简单地分析需求：

  1. 递增数组
  2. 最少右移次数
  3. x次右移是将下标i的元素移动到下标(i+x)%n处即可

• 如何满足上述的三个需求？

  1. 先将数组元素从小到大排序，得到最后的递增数组a[]

  2. 最少移动次数用数组遍历即可，x++;满足条件返回当前的x值即可。在移动一次后的当前答案后判断此时的数组元素是否和数组a[]每一位的元素相同即可。

  3. 判断此时移动后的数组元素和下标为(i+x)%n处的元素是否相同即可

  ​

---

1.3 具体代码

class Solution{
    public int minimumRightShift(List<Integer>nums){
        //注意题干给出恶的是List列表，此时获取nums中的元素用到get方法，长度用size()函数方法
        int n=nums.size();
        //a[]是当前排序好的结果元素，作为标准
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=nums.get(i);
        }
        Arrays.sort(a);
        //枚举需要右移的次数，同时开始每一位的判定
        for(int x=0;x<n;x++){//x若移动n次和0次的效果相同
            boolean flag=true;//用于判断每一次移动后的数组元素和标准数组的每一位是否相同，作为判断哨兵
            for(int i=0;i<n;i++){
                if(nums.get(i)!=a[(i+x)%n]){
                    f=false;
                    break;
                }
            }
            if(f){
                return x;//返回当前右移统计的次数
            }
        }
        return -1;//特例，没有则返回-1
    }
}

​

• 复杂度分析：

  • 时间复杂度：$O(n^2)$

    Arrays.sort(a)的时间复杂度为$O(nlogn)$,接下来两层循环的复杂度为$O(n^2)$。综上所述，时间复杂度为$O(n^2)$

  • 空间复杂度：$O(n)$

    在代码中，创建了一个长度为n的整型数组a来存储排好序的nums列表。由于nums列表和a数组的大小相同，因此需要额外的O(n)的空间。

---

​

T2. 删除数对后的最小数组长度

2.1 题目说明

给你一个下标从 0 开始的 非递减 整数数组 nums 。

你可以执行以下操作任意次：

• 选择 两个 下标 i 和 j ，满足 i < j 且 nums[i] < nums[j] 。
• 将 nums 中下标在 i 和 j 处的元素删除。剩余元素按照原来的顺序组成新的数组，下标也重新从 0 开始编号。

请你返回一个整数，表示执行以上操作任意次后（可以执行 0 次），nums 数组的 最小 数组长度。

示例 1：

输入：nums = [1,3,4,9]
输出：0
解释：一开始，nums = [1, 3, 4, 9] 。
第一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 1 < 3 。
删除下标 0 和 1 处的元素，nums 变成 [4, 9] 。
下一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 4 < 9 。
删除下标 0 和 1 处的元素，nums 变成空数组 [] 。
所以，可以得到的最小数组长度为 0 。

---

2.2 解答分析

• 注意审题，非递减数组说明可以存在相同的元素，比如数组[1,2,2,2,2,3,4,5,6]就满足条件

• 简化题干就是每次都需要删除一组的2个数，满足下标和数值不同，满足递增即可。其实就是寻找出现次数最多的数字，并记录它出现的次数。如果它出现的次数大于总数的一半，那么它一定无法被完全消去；否则判断数组长度的奇偶性，因为偶数可以一一匹配，消除掉，奇数则会存在一个剩余。

---

2.3 具体代码

class Solution{
    public int minLengthAfterRemovals(List<Integer> nums){
        //统计数组中相同元素出现的次数，找出出现次数最多的元素；首先判断是否可以被消除(也就是次数小于等于总数的一半)。如果行，则直接判断奇偶性即可；如果不行，计算最后剩余的次数
        HashMap<Integer,Integer> map=new HashMap<>();
        int max=0;
        for(int n:nums){
            int curcount=mao.getOrDefault(n,0)+1;
            max=Math.max(max,curcount);
            map.put(n,curcount);//每次遇到新的键、值都更新
        }
        int len=nums.size();
        if(2*max<=len){
            return len%2;//判断数组长度的奇偶性
        }else{
            return max-(len-max);////计算的是出现次数最多的数比其他数多的次数,也是最后多出来的次数
		}
    }
}

​

• 复杂度分析：

  • 时间复杂度：$O(n)$

    代码首先使用HashMap来统计每个数字出现的次数。在遍历nums列表时，对于每个数字n，将其出现次数记录在map中，并更新当前最大次数max。这个过程的时间复杂度是O(n)，因为需要遍历整个nums列表。根据出现次数max和数组长度len进行判断，得出最小长度的结果。这部分操作只涉及简单的数学运算和条件判断，时间复杂度为O(1)。

  • 空间复杂度：$O(k)/O(n)$

    对于空间复杂度，代码中使用了一个HashMap来存储数字和出现次数的映射关系，所占用的空间取决于nums列表中不同数字的个数，即O(k)，其中k是不同数字的数量。最坏的情况是O(n)，但是一般k会远小于n，随着n的不断增大。

​

---

T3. 统计距离为 k 的点对

3.1 题目说明

给你一个 二维 整数数组 coordinates 和一个整数 k ，其中 coordinates[i] = [xi, yi] 是第 i 个点在二维平面里的坐标。

我们定义两个点 (x1, y1) 和 (x2, y2) 的 距离 为 (x1 XOR x2) + (y1 XOR y2) ，XOR 指的是按位异或运算。

请你返回满足 i < j 且点 i 和点 j之间距离为 k 的点对数目。

示例 1：

输入：coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
输出：2
解释：以下点对距离为 k ：
- (0, 1)：(1 XOR 4) + (2 XOR 2) = 5 。
- (2, 3)：(1 XOR 5) + (3 XOR 2) = 5 。

示例 2：

输入：coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
输出：10
解释：任何两个点之间的距离都为 0 ，所以总共有 10 组点对。

提示：

• 2 <= coordinates.length <= 50000
• 0 <= xi, yi <= 10^6
• 0 <= k <= 100

​

---

3.2 解答分析

• 看到这个求和为k，想到的是两数之和，也就是要利用到HashMap进行遍历匹配。同时注意到提示条件中有0<=k<=100,说明此时可以枚举全部的$0\le x_1XORx_2\le 100$情况即可。

• 如何将对应的二维数组唯一确定呢？需要利用HashMap进行存储计算，记录每个坐标出现的次数。使用乘法因子mul对$(x_t,y_t)$转坏为唯一的find值，过查询countHashMap来获取find对应的值，并将其累加到res上。

• 将当前坐标（x, y）转换为唯一的key值，同样使用乘法因子mul，然后将key更新到countHashMap中，如果key已经存在，则将其对应值加1；如果key不存在，则初始化为1

• 本题是如何唯一确认二维坐标(xi, yi)的呢？这里设置比较大的乘法因子mul，设置成最大的值10^6,保证不会出现哈希碰撞导致键值对不唯一，确保生成的唯一数值范围足够广，以避免哈希冲突。。

  当有两个不同的二维坐标（xi1, yi1）和（xi2, yi2）满足xi1 + yi1 = xi2 + yi2时就会发生哈希冲突。

• 根据异或的性质，有 x ^ (i ^ x) = i, y ^ ((k - i) & y) = k - i，因此与 坐标 (x, y) 可以匹配的坐标是 (i ^ x, (k - i) ^ y)，其中 i 的取值范围是 0 ~ k。

​

---

3.3 具体代码

class Solution{
    private static final long mul=1000000;
    public int countPairs(List<List<Integer>> coordinates,int k){
        HashMap<Long,Integer>count =new HashMap<>();
        int res=0;
        for(List<Integer>coor:coordinates){
            int x=coor.get(0),y=coor.get(1);//获取当前点对的x和y的值
            
            for(int i=0;i<=k;i++){
                int xt=i^x,yt=(k-i)^y;//异或操作
                long find=xt*mul+yt;//乘法计算转化为唯一的find值
                res+=count.getOrDefault(find,0);//统计出现和为k的数对的次数
            }
            
            long key=x*mul+y;
            count.put(key,count.getOrDefault(key,0)+1);//将当前坐标出现的次数更新到HashMapcount中。如果key已存在，则将其对应的值加1；若不存在，则初始化为1。
        }
        return res;
    }
}

​

• 复杂度分析：

  • 时间复杂度：$O(N*k)$

    • 首先，遍历二维坐标列表需要花费O(N)的时间，其中N是坐标的数量。
    • 内部嵌套循环的时间复杂度是O(k)，因为它迭代了从0到k的i的所有可能取值。
    • 在内层循环中，通过HashMap的getOrDefault方法进行查询和更新操作，其时间复杂度是O(1)。
    • 因此，总体时间复杂度为O(N * k)。

  • 空间复杂度：$O(n)$

    创建一个HashMapcount用于记录每个坐标出现的次数，需要的空间是O(n)，其余地方并没有使用到额外的数据结构。

​

END~

继续努力！