MarsCode青训营序章Day1|稀土掘金-1.找单独的数、47.完美偶数计数、3.数组字符格式化

稀土掘金-1.找单独的数（1.找单独的数）

题目分析：

n个同学每人持有1张写有数字的卡片，除了一个数字之外，其他每个数字均出现了刚好2次，要求设计时间复杂度为O(n)的算法从cards数组中查找该单独的数。

题目重点：

已知除单独的数外，其余的都是成对的数，则不存在重复次数超过2的数。需要使时间复杂度为O(n)，考虑借助双指针法进行复杂度降阶。又因为使用双指针法需要数组有序，所以先对数组排序。

解题思路：

将数组按升序排序，用cur指针指向数组的首个元素，对比cur和cur+1的数是否相等，若相等则cur+=2，否则返回该数。需要检查边界条件，防止cur+1或cur+=2越界，只需使cur=cards.length-1时退出循环即可。

思路优化：

重新读题，发现数组排序步骤的.sort()方法的时间复杂度为O(nlongn)，超过了题目的时间复杂度要求。检查约束条件，发现测试样例的数组长度区间和数组元素取值区间均已给出，考虑借助约束条件设计新的排序算法如下：

基数排序：

基数排序（Radix Sort）是一种非比较型整数排序算法，适用于整数排序，特别是当整数的位数较少时。基数排序的时间复杂度为O(d * (n + k))，其中d是数字的最大位数，n是数组的长度，k是每个位可能的取值范围（例如0-9）。

import java.util.Arrays;

public class Main {
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        // 找出数组中的最大值
        int max = Arrays.stream(arr).max().getAsInt();

        // 从最低位开始，对每一位进行计数排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

        // 统计每个数字出现的次数
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        // 计算每个数字的累计次数
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 构建输出数组
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        // 将输出数组复制回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] cards = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(cards);
        System.out.println(Arrays.toString(cards));
    }
}

总结反思

基数排序虽然借助题目给出的约束条件实现了时间复杂度近似为O(n)的排序，但却也开拓了许多额外空间。

重新分析题目：时间复杂度要求为O(n)，说明不能使用排序，而是要从数本身的特性出发——每个数字要么成对，要么单独。我们需要一个漏斗，将唯一一个不是成对的数字筛出来，就像对对碰一样，让成对的数相消即可，这就让我们想到了异或的特性。

用一个result，将其初始化为0，遍历数组与每一个元素取异或。最终，每个相同的数取异或相消为0，每个新的数与0取异或得到自身，最终剩下来的result就是单独的数！

public class Main {
    public static int solution(int[] cards) {
        // Edit your code here
        int result = 0;
        for (int card : cards) {
            result ^= card;  // 使用异或操作
        }
        return result;
    }

    public static void main(String[] args) {
        // Add your test cases here
        
        System.out.println(solution(new int[]{1, 1, 2, 2, 3, 3, 4, 5, 5}) == 4);
        System.out.println(solution(new int[]{0, 1, 0, 1, 2}) == 2);
    }
}

稀土掘金-47.完美偶数计数（47.完美偶数计数）

题目分析：

完美偶数是一个在指定区间内的偶数，现欲求在长度为n的数组a中有多少个满足值区间为[l,r]的完美偶数。

题目重点：

直接遍历计数即可。

解题思路：

遍历数组中的每个元素，分别设置不为偶数、小于下界、大于上界的三个判断条件跳过该循环，否则result++

public class Main {
    public static int solution(int n, int l, int r, int[] a) {
        // write code here
        int result = 0;
        for (int i : a) {
            if (i % 2 != 0)
                continue;
            if (i < l)
                continue;
            if (i > r)
                continue;
            result++;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(solution(5, 3, 8, new int[] { 1, 2, 6, 8, 7 }) == 2);
        System.out.println(solution(4, 10, 20, new int[] { 12, 15, 18, 9 }) == 2);
        System.out.println(solution(3, 1, 10, new int[] { 2, 4, 6 }) == 3);
    }
}

稀土掘金-3.数组字符格式化（3.数组字符格式化）

题目分析：

将不带千分位逗号的数字字符串转换为带千分位逗号的格式，并保留小数部分。还需精简掉字符串前无用的0。

题目重点：

先精简无用0，再插入千分位逗号。

解题思路：

初始化一个StringBuilder sb。

用s.charAt(i)从左到右遍历字符串直至找到第一个不是无用0的字符将其append入sb，并记录其下标为left。

接着遍历剩余字符并将其append入sb，直至找到小数点或遍历字符串完全，将其append入sb，并记录其下标减一为right。

若仍有剩余字符，继续将其append入sb。

利用left和right，可以计算出有效整数位数和千分位逗号个数，将其从低到高找出最高的千分位逗号插入处，使用insert方法将其插入字符串，并从左到右每隔4个字符（包括新插入的逗号）将剩余逗号插入。

最终用toString()将该字符串导出。

总结反思

• 注意left和right作为有效整数部分区间的开闭
• 注意处理插入指针为0的特殊情况
• 注意插入指针的跨步数应为4（包括新插入的','）

public class Main {
    public static String solution(String s) {
        StringBuilder sb = new StringBuilder();
        if (s.length() == 0)
            return "";
        int cur = 0;
        int left = 0; // 整数部分的最高位
        int right = 0;// 整数部分的最低位
        int l = 0;    // 整数部分的长度
        int num = 0;  // 千分位逗号的个数

        while (cur < s.length() && s.charAt(cur) == '0'){ //精简无用'0'
            cur++;
        }
        left = cur; // 整数部分的最高位
        //System.out.println(left);

        while(cur < s.length()){
            sb.append(s.charAt(cur));
            if(s.charAt(cur) == '.')
                right = cur-1; // 整数部分的最低位
            cur++;
        }
        if(right == 0)
            right = s.length()-1; // 整数部分的最低位
        //System.out.println(right);
        l = right-left+1; // 整数部分的长度
        //System.out.println(l);
        num = l/3; // 千分位逗号的个数
        //System.out.println(num);
        cur = l%3; // 最高的千分位逗号下标
        //System.out.println(cur);
        if(cur == 0){
            cur+=3;
            num--;
        }
        while(num > 0){
            sb.insert(cur, ',');
            cur+=4;
            num--;
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(solution("1294512.12412").equals("1,294,512.12412"));
        System.out.println(solution("0000123456789.99").equals("123,456,789.99"));
        System.out.println(solution("987654321").equals("987,654,321"));
    }
}