稀土掘金-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 hereint result = 0;for (int card : cards) {result ^= card;  // 使用异或操作}return result;}public static void main(String[] args) {// Add your test cases hereSystem.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 hereint 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"));}
}