剑指 Offer第二版：1～n 整数中 1 出现的次数、51. 数组中的逆序对、56 - II. 数组中数字出现的次数 II

43. 1～n 整数中 1 出现的次数

题目：输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12
输出：5

**思路分析：**将n的每一位数分别处理，计算出每个位数上1的个数，然后将所有位数上1的个数相加即可。具体来说，首先判断n是否为0，如果n为0，直接返回0。然后从低位到高位依次处理每一位数，计算当前位数上1的个数。如果当前位数的数字小于1，1的个数为高位数当前位数，即highbit；如果当前位数的数字等于1，1的个数为高位数当前位数+低位数+1，即highbit+low+1；如果当前位数的数字大于1，1的个数为(high+1)*bit，即高位数加一乘以当前位数。最后将所有位数上1的个数相加即为最终结果。
时间复杂度：需要处理n的每一位数，因此时间复杂度为$O(\log n)$。
空间复杂度：只需要使用常量级别的额外空间，因此空间复杂度为$O(1)$。

class Solution {public int countDigitOne(int n) {if (n == 0) { // 如果n为0，直接返回0return 0;}long bit = 1; // bit表示当前处理的位数long cur = n / bit % 10; // cur表示当前处理的数字long low = n % bit; // low表示当前位数以下的数字long high = n / bit / 10; // high表示当前位数以上的数字long res = 0; // res表示1的个数while (bit <= n) { // 当位数小于等于n的位数时，继续处理if (cur < 1) { // 如果当前位数的数字小于1，1的个数为high*bitres += high * bit;} else if (cur == 1) { // 如果当前位数的数字等于1，1的个数为high*bit+low+1res += high * bit + low + 1;} else { // 如果当前位数的数字大于1，1的个数为(high+1)*bitres += (high + 1) * bit;}bit *= 10; // 处理下一位数cur = n / bit % 10;low = n % bit;high = n / bit / 10;}return (int) res; // 返回1的个数}
}

51. 数组中的逆序对

题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1：
输入: [7,5,6,4]
输出: 5

思路分析： 在归并排序的过程中，每次合并两个有序的子数组时，需要统计逆序对数量。具体实现时，在合并过程中，如果左半段的数大于等于右半段的数，则说明左半段中剩余的数都比右半段的数大，因此可以直接统计逆序对数量。
时间复杂度：归并排序的时间复杂度为O(nlogn)，而在归并排序的过程中，每次合并两个有序的子数组时，需要遍历所有元素一次，因此合并的时间复杂度也是O(nlogn)。因此总的时间复杂度为O(nlogn)。
空间复杂度：归并排序需要使用一个临时数组来存储合并过程中的数据，因此空间复杂度为O(n)。

class Solution {int res = 0; // 记录逆序对数量public int reversePairs(int[] nums) {if (nums == null || nums.length == 0) {return 0;}mergeSort(nums, 0, nums.length - 1); // 归并排序return res; // 返回逆序对数量}private void mergeSort(int[] nums, int l, int r) {if (l >= r) {return;}int mid = (r - l) / 2 + l; // 计算中间位置mergeSort(nums, l, mid); // 对左半段进行归并排序mergeSort(nums, mid + 1, r); // 对右半段进行归并排序merge(nums, l, mid, r); // 合并左右两个有序的子数组}private void merge(int[] nums, int l, int mid, int r) {int i = l; // 左半段的起始位置int j = mid + 1; // 右半段的起始位置int[] temp = new int[r - l + 1]; // 用于存储合并过程中的数据int index = 0; // 临时数组的下标while (i <= mid && j <= r) { // 合并左右两个有序的子数组if (nums[i] <= nums[j]) { // 如果左半段的数小于右半段的数temp[index++] = nums[i++]; // 将左半段的数加入临时数组中} else { // 如果左半段的数大于等于右半段的数res += mid - i + 1; // 统计逆序对数量temp[index++] = nums[j++]; // 将右半段的数加入临时数组中}}// 将剩余的元素复制到临时数组中while (i <= mid) {temp[index++] = nums[i++];}while (j <= r) {temp[index++] = nums[j++];}// 将临时数组中的元素复制回原数组中index = 0;for (i = l; i <= r; i++) {nums[i] = temp[index++];}}
}

56 - II. 数组中数字出现的次数 II

题目：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4

思路分析： 对于每一位，统计所有数字在该位上出现的次数，然后对3取模，得到出现1次的数字在该位上的值。最后将所有位的值合并起来，即得到最终结果。
时间复杂度为O(nk)，其中n为数字数量，k为数字的二进制位数，因为需要遍历所有数字和所有位数。
空间复杂度为O(k)，因为需要使用一个长度为k的数组来记录每个数字在每个位上出现的次数。

class Solution {public int singleNumber(int[] nums) {if(nums == null || nums.length == 0){return -1;}int res = 0; // 用于存储最终结果int bit = 1; // 用于表示当前位的值，从最低位开始int[] count = new int[32]; // 用于记录所有数字在当前位上出现的次数for(int i = 0; i < 32; i++){ // 遍历所有位for(int j = 0; j < nums.length; j++){ // 遍历所有数字if((nums[j] & bit) != 0){ // 如果当前数字在当前位上为1count[i]++; // 记录出现次数}}count[i] %= 3; // 对3取模，得到出现1次的数字在当前位上的值res += bit * count[i]; // 将当前位的值加入最终结果bit <<= 1; // 判断下一位}return res; // 返回最终结果}
}