给定一个int数组A和它的大小n，对于这组数能组成的任意两个数组，若前面一个大于后面一个数字，则这两个数字组成一个逆序对。请设计一种高效的算法返回A中存在的逆序对个数。要求n不大于5000。
测试样例：
[1,2,3,4,5,6,7,0],8
返回：7
[编程题]数组中的逆序对
import java.util.*;
//这个题和上一个求数组的秩是类似的，逆序对=当前数组长度 - 秩，
//在秩的基础上，把左右子树对调一下就可以了，在秩的基础上修改两个不等号就ok了
public class AntiOrder {
Node root = null;
public int count(int[] A, int n) {
int res = 0;
for (int i = 0; i < n; i++) {
res += helper(A[i]);
}
return res;
}
public int helper(int a) {
if (root == null) {
root = new Node(a);
return 0;
} else {
root.insert(a);
return root.getRank(a);
}
}
}
class Node {
int leftSize = 0;
Node left, right;
int val;
public Node(int v) {
val = v;
}
public void insert(int v) {
if (v > val) {
if (left != null)
left.insert(v);
else
left = new Node(v);
leftSize++;
} else {
if (right != null)
right.insert(v);
else
right = new Node(v);
}
}
public int getRank(int v) {
if (v == val)
return leftSize;
if (v > val)
return left.getRank(v);
if (v < val)
return leftSize + 1 + right.getRank(v);
return 0;
}
}
发表于 2015-09-10 15:32:38
回复(0)
/*
[1,2,3,4,5,6,7,0],8
7
类似11.8,也可以用multiset(底层为红黑树)做,
以0为例,end-cur即为0的逆序对数目
*/
class AntiOrder {
public:
int count(vector<int> A, int n) {
// write code here
int ret = 0;
multiset<int> mset;
multiset<int>::iterator cur, end;
for (int i = 0; i < n; i++)
{
mset.insert(A[i]);
cur = mset.upper_bound(A[i]);
end = mset.end();
while (cur != end)
{
ret++;
cur++;
}
}
return ret;
}
};
发表于 2017-02-21 10:55:15
回复(0)
int merge(int[] A, int start, int mid, int end) {
int[] aux = new int[end - start + 1];
int i = start;
int j = mid + 1;
int k = 0;
int reverse = 0;
while (i <= mid && j <= end) {
if (A[i] <= A[j]) {
aux[k++] = A[i++];
} else {
reverse += mid - i + 1;
aux[k++] = A[j++];
}
}
while (i <= mid) {
aux[k++] = A[i++];
}
while (j <= end) {
aux[k++] = A[j++];
}
for (int m = 0; m < aux.length; ++m) {
A[start + m] = aux[m];
}
return reverse;
}
public int count(int[] A, int start, int end) {
if (end <= start) {
return 0;
}
int mid = (start + end) >> 1;
int count1 = count(A, start, mid);
int count2 = count(A, mid + 1, end);
return count1 + count2 + merge(A, start, mid, end);
}
public int count(int[] A, int n) {
// write code here
return count(A, 0, n - 1);
}
发表于 2016-04-27 20:50:17
回复(0)
class AntiOrder {
public:
//归并排序，前面一块数据中没出现一个值比后面值的数，则前面之后的数都比后面的该数大
void merge_sort(vector& A,int start,int end,vector& tmp,int& count)
{
if(start == end)
return;
int mid = (start+end)/2;
merge_sort(A,start,mid,tmp,count);
merge_sort(A,mid+1,end,tmp,count);
int i=start,j=mid+1;
int ind = start;
while(i<=mid && j<=end)
{
if(A[i] > A[j])
{
count += mid-i+1;
tmp[ind++] = A[j++];
}else
{
tmp[ind++] = A[i++];
}
}
while(i <= mid)
{
tmp[ind++] = A[i++];
}
while(j <= end)
{
tmp[ind++] = A[j++];
}
for(int k=start;k<=end;++k)
{
A[k] = tmp[k];
}
}
int count(vector A, int n) {
// write code here
vector tmp(n,0);
int num = 0;
merge_sort(A,0,n-1,tmp,num);
return num;
}
};
发表于 2020-07-21 23:25:17
回复(0)
import java.util.*;
//其实也就是求一个数左边有少个比它大的，排序后p2之前的数就是p2的所有逆序对 （R-p2+1）
public class AntiOrder {
public int count(int[] A,int n) {
if(A == null || n == 0) return 0;
return mergSort(A,0,A.length-1);
}
public int mergSort(int[] arr,int L,int R){
if(L == R) return 0;
int mid = L+ ((R-L) >> 1);
return mergSort(arr,L,mid)+mergSort(arr,mid+1,R)+merg(arr,L,mid,R);
}
public int merg(int[] arr,int L,int mid,int R){
int[] help = new int[R-L+1];
int i = 0;
int count = 0;
int p1 = L;
int p2 = mid+1;
while(p1 <= mid && p2 <= R){
if(arr[p1] > arr[p2]){
count += (mid-L)+1;
help[i++] = arr[p2++];
}else{
help[i++] = arr[p1++];
}
}
while(p1 <= mid){
help[i++] = arr[p1++];
}
while(p2 <= R){
help[i++] = arr[p2++];
}
for (int j = 0; j < help.length; j++) {
arr[L + j] = help[j];
}
return count;
}
}
编辑于 2021-03-18 18:24:33
回复(0)
import java.util.*;
/*
错误的思路：先排序，再对比排序后的数字和排序前的数字位置，相同数字在不同位置之间的位置差的数目就是逆序对的数目
如何找相同数字的不同位置~用二分法可以降复杂度，时间复杂度O（nlogn）
很想知道我这个思路哪里错了啊！！！求大神解释
正确的思路：归并排序
*/
/*
public class AntiOrder {
public int count(int[] A, int n) {
int b[] =new int[n];
int j=0;
int sum=0;
for(int m:A){
b[j]=m;
j++;
}
Arrays.sort(b);
for(j=0;j<n;j++){
int start=0;
int end =n-1;
int mid=0;
while(start<=end){
mid =(start+end)/2;
if(A[j]==b[mid]) break;
else if(A[j]>b[mid]) start=mid+1;
else end =mid-1;
}
if(mid-j>0) sum=sum+mid-j;
}
return sum;
}
}
*/
public class AntiOrder {
public int count(int[] A, int n) {
if(A==null||A.length==0) return 0;
int []copy=new int[n];
for(int i=0;i<n;i++){
copy[i]=A[i];
}
return mergesort(A,copy,0,n-1);
}
public int mergesort(int[] A,int[] copy,int start,int end){
if(start==end){
copy[start] =A[start];
return 0;
}
int mid=(start+end)/2;
int left =mergesort(copy,A,start,mid);
//这里要注意了，copy和A的数组互换了,实际上我们比较的都是copy中的数组值，而不是A的数组值
//因为copy中数组是一直保持分段数组内部顺序的（即每次逆序对计算完，都会把计算完的逆序对顺序调整）
//用copy数组比较才不会出现重复计算逆序对的情况，这里如果不互换顺序会多计算无数次逆序对
int right =mergesort(copy,A,mid+1,end);
int i=mid,j=end,count=0,index=end;
while(i>=start&&j>mid){
if(A[i]>A[j]){
count +=j-mid;
copy[index--]=A[i--];
}else{
copy[index--]=A[j--];
}
}
while(i>=start){
copy[index--]=A[i--];
}
while(j>mid){
copy[index--]=A[j--];
}
return count+left+right;
}
}
运行时间：205ms
占用内存：13612k
发表于 2017-07-05 17:17:56
回复(0)
归并排序
class AntiOrder {
public:
int mergeSort(vector<int>& A, vector<int>& temp, int left, int right)
{
if (left >= right) return 0;
int reverseCount = 0;
int mid = (left + right) >> 1;
reverseCount += mergeSort(A, temp, left, mid);
reverseCount += mergeSort(A, temp, mid + 1, right);
int pos, i, j;
for (pos = left,i = left, j = mid + 1; j <= right; ++j)
{
while (i <= mid && A[i] < A[j])
{
temp[pos] = A[i];
++pos;
++i;
}
if (i <= mid) reverseCount += mid - i + 1;
temp[pos] = A[j];
++pos;
}
while (i <= mid) temp[pos++] = A[i++];
memcpy(A.data() + left, temp.data() + left, (right - left + 1) * sizeof(int));
return reverseCount;
}
int count(vector<int> A, int n)
{
vector<int> temp(n, 0);
return mergeSort(A, temp, 0, n - 1);
}
};
发表于 2017-06-30 14:46:22
回复(0)
class AntiOrder:
def count(self, A, n):
self.rNums = 0
self.mergeSort(A)
return self.rNums
def mergeSort(self, A):
if len(A) <= 1:
return A
m = len(A) / 2
a = self.mergeSort(A[:m])
b = self.mergeSort(A[m:])
return self.merge(a, b)
def merge(self, A, B):
c, i, j = [], 0, 0
while i < len(A) and j < len(B):
if A[i] <= B[j]:
c.append(A[i])
i += 1
else:
c.append(B[j])
j += 1
self.rNums += len(A) - i #此为逆序对数
c += A[i:]
c += B[j:]
return c
发表于 2017-03-05 13:53:15
回复(0)
class AntiOrder {
public:
int count(vector<int> data, int n) {
// write code here
if(data.size()<=1) return 0;
int* copy=new int[data.size()];
//初始化数组
for(unsigned int i=0;i<data.size();i++)
copy[i]=0;
int count=InversePairCore(data,copy,0,data.size()-1);
delete[] copy;
return count;
}
int InversePairCore(vector<int>& data,int*& copy,int start,int end)
{
if(start==end)
{
copy[start]=data[start];
return 0;
}
//将数组拆分成两部分
int length=(end-start)/2;
//分别计算左边部分和右边部分
int left=InversePairCore(data,copy,start,start+length)%1000000007;
int right=InversePairCore(data,copy,start+length+1,end)%1000000007;
//进行逆序计算
int i=start+length;
int j=end;
int index=end;
int count=0;
while(i>=start && j>=start+length+1)
{
if(data[i]>data[j])
{
copy[index--]=data[i--];
//统计长度
count+=j-start-length;
if(count>=1000000007)//数值过大求余
count%=1000000007;
}
else
{
copy[index--]=data[j--];
}
}
for(;i>=start;--i)
{
copy[index--]=data[i];
}
for(;j>=start+length+1;--j)
{
copy[index--]=data[j];
}
//排序
for(int i=start; i<=end; i++) {
data[i] = copy[i];
}
//返回最终的结果
return (count+left+right)%1000000007;
}
};
发表于 2016-08-14 17:32:58
回复(0)
/*
* 数组的逆序对就是当前数组长度-秩，与上题一样，维护一组二叉查找树，每次添加新值后得到该数组对应的秩，用当前数组长度-秩
* 对所有值的添加过程都进行逆序对计算，并加和即可
*/
public class RankNode{
public int left_size = 0;
public RankNode left, right;
public int data = 0;
public RankNode(int d) {
// TODO Auto-generated constructor stub
data = d;
}
public void insert(int d) {
// TODO Auto-generated method stub
if(d <= data){
if(left != null){
left.insert(d);
}else{
left = new RankNode(d);
}
left_size++;
}else{
if(right != null){
right.insert(d);
}else{
right = new RankNode(d);
}
}
}
public int getRank(int d) {
// TODO Auto-generated method stub
if(d == data){
return left_size;
}else if(d < data){
if(left == null){
return -1;
}else{
return left.getRank(d);
}
}else{
int right_rank = right == null ? -1 : right.getRank(d);
if(right_rank == -1) return -1;
return left_size + 1 + right.getRank(d);
}
}
}
public int count(int[] A, int n) {
// write code here
if(A == null || A.length != n || n <= 0){
return 0;
}
RankNode root = new RankNode(A[0]);
int[] ranks = new int[n];
int res = 0;
for(int i = 1; i < n; i++){
root.insert(A[i]);
ranks[i] = root.getRank(A[i]);
res += i - ranks[i];
}
return res;
}
发表于 2016-06-11 23:32:44
回复(0)
Solution: 提供两种解决方案：
Method 1: brute force O(n^2)
Method 2: merge sort O(nlogn)
publicintcount(int[] A, intn) {
// write code here
if(A==null|| n==0) return0;
//Method 2: merge sort
returnhelper(A,0,n-1);
/*
//Method 1: brute force O(n^2)
int count=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(A[i]>A[j]){
count++;
}
}
}
return count;
*/
}
privateinthelper(int[] A, intstart, intend){
if(start>=end) return0;
intmid=start + (end-start)/2;
intleft=helper(A,start, mid);
intright=helper(A,mid+1,end);
intcount=mergeCount(A,start,mid,end);
returnleft+count+right;
}
privateintmergeCount(int[] A, intstart, intmid, intend){
intresult=0;
int[] t=newint[end+1];
for(inti=start;i<=end;i++){
t[i]=A[i];
}
inti=mid,j=end;
intk=end;
while(i>=start && j>=mid+1){
if(A[i]>=A[j]){
t[k--]=A[i--];
result+= j-mid;
}else{
t[k--]=A[j--];
}
}
while(i>=start){
t[k--]=A[i--];
}
while(j>mid){
t[k--]=A[j--];
}
for(intm=start;m<=end;m++){
A[m]=t[m];
}
returnresult;
}
发表于 2016-01-02 15:46:13
回复(0)
大概思路是归并排序的思想，先分为2个左右部分，左部分的逆序对(只在左部分取2个数)，右部分的逆序对(只在右部分取2个数)，满足在左部分取一个数，右部分取一个数的逆序对，以上全部加起来就是总的逆序对。计算左右部分的逆序对的时候，利用递归。
class Solution {
public:
int InversePairs(vector<int> data) {
return merge(data, 0, data.size() - 1);
}
int merge_count(vector<int> &data, int start, int mid, int end)//计算满足左部分一个数，右部分一个数条件的逆序对,此时左右部分已排好序
{
vector<int> temp(data);
int count = 0;
int i = start;
int j = mid + 1;
int k = start;
while (i <= mid&&j <= end)
{
if (data[i] <=data[j])
temp[k++] = data[i++];
else
{
temp[k++] = data[j++];
count = count + mid- i+1;
}
}
while (i <= mid)temp[k++] = data[i++];
while (j <= end)temp[k++] = data[j++];
for (int m = start; m <= end; m++)
data[m] = temp[m];
return count;
}
int merge(vector<int> &data, int start, int end)//左右部分分别递归，
{
if (start >= end)
return 0;
int mid = (start + end) / 2;
int left=merge(data, start, mid);
int right=merge(data, mid + 1, end);
int count = merge_count(data, start, mid, end);
return left + right + count;
}
};
发表于 2015-11-04 10:04:32
回复(0)
//常规思想，找出每个元素的逆序对，复杂度是O(N*N)
//利用归并排序的思想，先划分再合并，复杂度可以降到O(NlogN)
class AntiOrder {
public:
void merge(vector<int> &v,int a1,int a2,int b1,int b2,int &pairs){
vector<int> tmp;
int i=a1;
int j=b1;
while(i<=a2&&j<=b2){
if(v[i]<=v[j]){
tmp.push_back(v[i++]);
pairs=pairs+j-b1;
}
else{
tmp.push_back(v[j++]);
}
}
while(i<=a2){
tmp.push_back(v[i++]);
pairs=pairs+b2-b1+1;
}
while(j<=b2) tmp.push_back(v[j++]);
for(i=0,j=a1;j<=b2;j++)
v[j]=tmp[i++];
}
void fun(vector<int> &v,int p1,int p2,int &pairs){
if(p1==p2)
return;
fun(v,p1,(p1+p2)/2,pairs);
fun(v,(p1+p2)/2+1,p2,pairs);
merge(v,p1,(p1+p2)/2,(p1+p2)/2+1,p2,pairs);
}
int count(vector<int> A, int n) {
int pairs=0;
fun(A,0,n-1,pairs) ;
return pairs;
}
};
编辑于 2015-10-19 21:07:34
回复(0)
利用归并排序，在对有序子数组进行merge的同时，累加逆序对，时间复杂度O(nlogn)
import java.util.*; public class AntiOrder { public int count(int[] A, int n) { // write code here if (A == null || n == 0) { return 0; } return mergeSortRecursion(A, 0, n - 1); } /** * 递归实现归并排序 * * @param arr * @param l * @param r * @return 返回数组中的逆序对 */ public static int mergeSortRecursion(int[] arr, int l, int r) { if (l == r) { // 当待排序数组长度为1时，递归开始回溯，进行merge操作 return 0; } int mid = (l + r) / 2; return mergeSortRecursion(arr, l, mid) + mergeSortRecursion(arr, mid + 1, r) + merge(arr, l, mid, r); } /** * 合并两个已排好序的数组s[left...mid]和s[mid+1...right] * * @param arr * @param left * @param mid * @param right * @return 返回合并过程中累加逆序对 */ public static int merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; // 辅助存储空间 O(n) int index = 0; int i = left; int j = mid + 1; int inverseNum = 0; // 新增，用来累加数组逆序对 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[index++] = arr[i++]; } else { // 当前一个数组元素大于后一个数组元素时，累加逆序对 // s[i] > s[j] -> s[i]...s[mid] > s[j] inverseNum += (mid - i + 1); temp[index++] = arr[j++]; } } while (i <= mid) { temp[index++] = arr[i++]; } while (j <= right) { temp[index++] = arr[j++]; } for (int k = 0; k < temp.length; k++) { arr[left++] = temp[k]; } return inverseNum; } }
编辑于 2017-07-28 15:08:55
回复(4)
# -*- coding:utf-8 -*- class AntiOrder: def count(self, A, n): # write code here self.res = 0 # 调用归并排序计算逆序数 self.mergeSort(A) return self.res def mergeSort(self, A): if len(A) <= 1: return A # 递归结束 mid = len(A) // 2 left = self.mergeSort(A[:mid]) # 左边排好序 right = self.mergeSort(A[mid:]) # 右边排好序 merged = [] while left and right: if left[0] <= right[0]: merged.append(left.pop(0)) else: self.res += len(left) # 逆序数 merged.append(right.pop(0)) # 剩余部分放在数组后面 merged.extend(right if right else left) return merged
发表于 2020-12-13 13:25:33
回复(0)
问题信息
难度：
60条回答
80收藏
31566浏览
通过挑战的用户
查看代码-
2023-03-07 17:12:41
-
2023-03-03 01:55:30
-
2022-10-31 23:41:37
-
2022-10-26 20:52:32
-
2022-09-13 19:26:15
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
