剑指 Offer 51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:输入: [7,5,6,4]输出: 5限制：0 <= 数组长度 <= 50000
分治算法
详解见leetcode
利用归并排序的方法，先求左半部分的逆序对，再求右半部分的逆序对，最后求整个数列的逆序对。
class Solution {
public int reversePairs(int[] nums) {
int len = nums.length;
if (len < 2) {
return 0;
}
// 如果不能在nums修改，就copy一下nums
int[] copy = new int[len];
for (int i = 0; i < len; i++) {
copy[i] = nums[i];
}
int[] temp = new int[len];
return reversePairs(copy, 0, len - 1, temp);
}
private int reversePairs(int[] nums, int left, int right, int[] temp) {
if (left == right) {
return 0;
}
int mid = left + ((right - left) >> 1);
int leftPairs = reversePairs(nums, left, mid, temp);
int rightPairs = reversePairs(nums, mid + 1, right, temp);
if (nums[mid] <= nums[mid + 1]) {
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(nums, left, mid, right, temp);
return crossPairs + leftPairs + rightPairs;
}
private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int i = left;
int j = mid + 1;
int count = 0;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {
nums[k] = temp[j];
j++;
} else if (j == right + 1) {
nums[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {
nums[k] = temp[i];
i++;
} else {
nums[k] = temp[j];
j++;
count += mid - i + 1;
}
}
return count;
}
}
剑指 Offer 56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：
2 <= nums.length <= 10000
位运算
异或满足交换律，第一步异或，相同的数其实都抵消了，剩下两个不同的数。这两个数异或结果肯定有某一位为1，不然都是0的话就是相同数。找到这个位，不同的两个数一个在此位为0，另一个为1。按此位将所有数分成两组，分开后各自异或，相同的两个数异或肯定为0（而且分开的时候，两个数必为一组）。剩下的每组里就是我门要找的数。
class Solution {
public int[] singleNumbers(int[] nums) {
// 用于将所有的数异或起来
int k = 0;
for (int num : nums) {
k ^= num;
}
// 获得k中最低位的1
int mask = 1;
while ((k & mask) == 0) {
mask <<= 1;
}
// first、second为两个不同的数
int first = 0;
int second = 0;
// first、second中有一个数的二进制形式最后一个1和mask相同，所有可以将这两个数分开
for (int num : nums) {
if ((num & mask) == 0) {
first ^= num;
} else {
second ^= num;
}
}
return new int[]{first, second};
}
}
剑指 Offer 56 - II. 数组中数字出现的次数 II
剑指 Offer 56 - II. 数组中数字出现的次数 II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
限制：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31
位运算
如果一个数字出现三次,那么它的二进制表示的每一位(0或者1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1;
上述思路同样适用于数组中一个数字出现一次，其他数字出现奇数次问题(如果是偶数次，直接用异或就可)。
class Solution {
public int singleNumber(int[] nums) {
if (nums.length == 0) {
return -1;
}
int[] bitSum = new int[32];
int res = 0;
for (int num : nums) {
int bitMask = 1;
for (int i = 31; i >= 0; i--) {
if ((num & bitMask) != 0) {
bitSum[i]++;
}
bitMask = bitMask << 1;
}
}
for (int i = 0; i < 32; i++) {
res = res << 1;
res += bitSum[i] % 3;
}
return res;
}
}
剑指 Offer 57. 和为s的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
限制：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
双指针
class Solution {
public int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while (i < j) {
int s = nums[i] + nums[j];
if (s < target) {
i++;
} else if (s > target) {
j--;
} else {
return new int[] {nums[i], nums[j]};
}
}
return new int[0];
}
}
剑指 Offer 57 - II. 和为s的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5
双指针
left 到 right之间的和sum
- sum < target, right++
- sum > target, left++
- sum == target, 添加结果，left++，因为从left开始只有一个符号条件。
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> res = new ArrayList<>();
for (int left = 1, right = 2; left < right;) {
int sum = (left + right) * (right - left + 1) / 2;
if (sum == target) {
int[] tmp = new int[right - left + 1];
for (int i = left; i <= right; i++) {
tmp[i - left] = i;
}
res.add(tmp);
left++;
} else if (sum < target) {
right++;
} else {
left++;
}
}
return res.toArray(new int[res.size()][]);
}
}
推荐阅读
若有收获，就点个赞吧
0 人点赞
