admin管理员组文章数量:1031252
分治
题目：
链接: link
这题和逆序对区别点就是，要找到前一个元素是后一个元素的2倍 先找到目标值再，继续堆排序
解析：
策略一：
代码：
代码语言：javascript代码运行次数：0运行复制class Solution {
int[] tmp;
public int reversePairs(int[] nums) {
int n = nums.length;
tmp = new int[n];
return mergesort(nums,0,n-1);
}
private int mergesort(int[] nums, int left, int right){
int ret = 0;
if(left >= right) return 0;
int mid = (right + left) / 2;
//左右两边找翻转对
ret += mergesort(nums,left,mid);
ret += mergesort(nums,mid+1,right);
//一左一右找翻转对: 降序版本
//输入数组中的所有数字都在32位整数的表示范围内:改为：2.0*nums[cur2]
int cur1 = left, cur2 = mid+1, i = 0;
while(cur1 <= mid && cur2 <= right){
if(nums[cur1] <= 2.0*nums[cur2]){
cur2++;
}else {
ret += right - cur2 + 1;
cur1++;
}
if(cur2 > right) break;
}
//排序：
cur1 = left; cur2 = mid+1;
while(cur1 <= mid && cur2 <= right)
tmp[i++] = nums[cur1] <= nums[cur2]? nums[cur2++] : nums[cur1++];
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
//放回原数组：
for(int j = left; j <= right; j++){
nums[j] = tmp[j-left];
}
return ret;
}
}策略二：
代码：
代码语言：javascript代码运行次数：0运行复制class Solution {
int[] tmp;
public int reversePairs(int[] nums) {
int n = nums.length;
tmp = new int[n];
return mergesort(nums,0,n-1);
}
一左一右找翻转对: 升序版本:
private int mergesort(int[] nums, int left, int right){
int ret = 0;
if(left >= right) return 0;
int mid = (right + left) / 2;
//左右两边找翻转对
ret += mergesort(nums,left,mid);
ret += mergesort(nums,mid+1,right);
//一左一右找翻转对: 升序版本
//输入数组中的所有数字都在32位整数的表示范围内:改为：2.0*nums[cur2]
int cur1 = left, cur2 = mid+1, i = 0;
while(cur1 <= mid && cur2 <= right){
if(nums[cur1] / 2.0 <= nums[cur2]){
cur1++;
}else {
ret += mid - cur1 + 1;
cur2++;
}
if(cur1 > mid) break;
}
//排序：
cur1 = left; cur2 = mid+1;
while(cur1 <= mid && cur2 <= right)
tmp[i++] = nums[cur1] <= nums[cur2]? nums[cur1++] : nums[cur2++];
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
//放回原数组：
for(int j = left; j <= right; j++){
nums[j] = tmp[j-left];
}
return ret;
}
}分治
题目：
链接: link
这题和逆序对区别点就是，要找到前一个元素是后一个元素的2倍 先找到目标值再，继续堆排序
解析：
策略一：
代码：
代码语言：javascript代码运行次数：0运行复制class Solution {
int[] tmp;
public int reversePairs(int[] nums) {
int n = nums.length;
tmp = new int[n];
return mergesort(nums,0,n-1);
}
private int mergesort(int[] nums, int left, int right){
int ret = 0;
if(left >= right) return 0;
int mid = (right + left) / 2;
//左右两边找翻转对
ret += mergesort(nums,left,mid);
ret += mergesort(nums,mid+1,right);
//一左一右找翻转对: 降序版本
//输入数组中的所有数字都在32位整数的表示范围内:改为：2.0*nums[cur2]
int cur1 = left, cur2 = mid+1, i = 0;
while(cur1 <= mid && cur2 <= right){
if(nums[cur1] <= 2.0*nums[cur2]){
cur2++;
}else {
ret += right - cur2 + 1;
cur1++;
}
if(cur2 > right) break;
}
//排序：
cur1 = left; cur2 = mid+1;
while(cur1 <= mid && cur2 <= right)
tmp[i++] = nums[cur1] <= nums[cur2]? nums[cur2++] : nums[cur1++];
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
//放回原数组：
for(int j = left; j <= right; j++){
nums[j] = tmp[j-left];
}
return ret;
}
}策略二：
代码：
代码语言：javascript代码运行次数：0运行复制class Solution {
int[] tmp;
public int reversePairs(int[] nums) {
int n = nums.length;
tmp = new int[n];
return mergesort(nums,0,n-1);
}
一左一右找翻转对: 升序版本:
private int mergesort(int[] nums, int left, int right){
int ret = 0;
if(left >= right) return 0;
int mid = (right + left) / 2;
//左右两边找翻转对
ret += mergesort(nums,left,mid);
ret += mergesort(nums,mid+1,right);
//一左一右找翻转对: 升序版本
//输入数组中的所有数字都在32位整数的表示范围内:改为：2.0*nums[cur2]
int cur1 = left, cur2 = mid+1, i = 0;
while(cur1 <= mid && cur2 <= right){
if(nums[cur1] / 2.0 <= nums[cur2]){
cur1++;
}else {
ret += mid - cur1 + 1;
cur2++;
}
if(cur1 > mid) break;
}
//排序：
cur1 = left; cur2 = mid+1;
while(cur1 <= mid && cur2 <= right)
tmp[i++] = nums[cur1] <= nums[cur2]? nums[cur1++] : nums[cur2++];
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
//放回原数组：
for(int j = left; j <= right; j++){
nums[j] = tmp[j-left];
}
return ret;
}
}本文标签： 分治
版权声明：本文标题：分治 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1747723291a2209071.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论