[数据结构与算法]单周赛 2022.1.23 题解汇总

T1?5989. 元素计数

给你一个整数数组 nums ，统计并返回在 nums 中同时具有一个严格较小元素和一个严格较大元素的元素数目。

?

提示：

• 1 <= nums.length <= 100
• -105?<= nums[i] <= 105

解题思路：按照题意，我们只需要对题目数组进行排序，然后用数组元素的总个数减去最大以及最小元素的个数，即为所求答案。因为只有最大最小值是严格最大元素和严格最小元素不能够同时拥有的。

代码和提交截图如下：

class Solution {
    public int countElements(int[] nums) {
        Arrays.sort(nums);
        int min = nums[0];
        int max = nums[nums.length-1];
        int count = nums.length;
        for(int i = 0 ; i < nums.length ; i++){
            if(nums[i] == min || nums[i] == max){
                count--;
            }
        }
        return count;
    }
}

?

T2?5991. 按符号重排数组?

给你一个下标从 0 开始的整数数组 nums ，数组长度为 偶数 ，由数目相等的正整数和负整数组成。

你需要 重排 nums 中的元素，使修改后的数组满足下述条件：

任意?连续 的两个整数 符号相反
对于符号相同的所有整数，保留 它们在 nums 中的 顺序 。
重排后数组以正整数开头。
重排元素满足上述条件后，返回修改后的数组。

?

提示：

• 2 <= nums.length <= 2 * 105
• nums.length 是 偶数
• 1 <= |nums[i]| <= 105
• nums 由 相等 数量的正整数和负整数组成

解题思路：① 将一直数组按照元素的顺序将正负元素拆分，并且存储到两个数组当中。

? ? ? ? ? ? ? ? ? ② 然后将两个数组再按照要求一个一个添加进新数组返回即可。

? ? ? ? ? ? ? ? ? 完全没有一个中等题的难度，应该是有更优秀的做法，但是这个方法可以ac，只不过开了辅助空间。

代码和提交结果如下：

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int zheng[] = new int[nums.length/2];
        int fu[] = new int[nums.length/2];
        int res[] = new int[nums.length];
        int zhengIndex = 0;
        int fuIndex = 0;
        for(int i = 0 ; i < nums.length ; i++){
            if(nums[i] > 0){
                zheng[zhengIndex] = nums[i];
                zhengIndex++;
            }else{
                fu[fuIndex] = nums[i];
                fuIndex++;
            }
        }
        zhengIndex = 0;
        fuIndex = 0;
        for(int i = 0 ; i < res.length ; i++){
            if(i % 2 == 0){
                res[i] = zheng[zhengIndex++];
            }else{
                res[i] = fu[fuIndex++];
            }
        }
        return res;
    }
}

?

T3?5990. 找出数组中的所有孤独数字?

给你一个整数数组 nums 。如果数字 x 在数组中仅出现 一次 ，且没有 相邻 数字（即，x + 1 和 x - 1）出现在数组中，则认为数字 x 是 孤独数字 。

返回 nums 中的 所有 孤独数字。你可以按 任何顺序 返回答案。

?

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 106

解题思路：① 遍历数组使用HashMap将所有的元素以元素值为 key，个数为 value 存储。

? ? ? ② 重新遍历数组，如果元素的个数等于 1 ，并且 map 不包括元素 - 1 和 元素 + 1 的 key 的情况下，将该元素添加进用来返回的结果集List中，遍历完返回即可。?

其实应该也可以使用数组进行操作，一遍遍历数组即可，但是打比赛先想到了这个方法，并且好写代码，感觉这个题也是没有中等难度。上面的方法在求数组最长连续子序列的长度那道题也可以用。

代码和提交结果如下：

class Solution {
    public List<Integer> findLonely(int[] nums) {
        List<Integer> res = new ArrayList();
        HashMap<Integer,Integer> map = new HashMap();
        for(int i = 0 ; i < nums.length ; i++){
            map.put(nums[i] , map.getOrDefault(nums[i],0) + 1);
        }
        for(int i = 0 ; i < nums.length ; i++){
            if(map.get(nums[i]) != 1){
                continue;
            }else{
                int index = nums[i];
                if(!map.containsKey(index-1) && !map.containsKey(index+1)){
                    res.add(nums[i]);
                }
            }
        }
        return res;
    }
}

?

T4 想啥呢，等啥时候能写出来 T4 那才是质变。

本周单周赛总结：题目偏简单，主要考察数组，加油。??