用c++实现数组的反转计数指示, 数组排序的距离。如果数组已经排序,则反转计数为0,但是如果数组以相反顺序排序,则反转计数为最大值。 如果a [i]> a [j]且i <j,则两个元素a [i]和a [j]构成一个倒置
时间: 2023-12-28 13:03:38 浏览: 68
C++实现将数组中的值反转
好的,我理解了你的问题。下面是用C++实现数组的反转计数指示和数组排序的距离的代码:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int reverseCount(vector<int>& nums) {
int n = nums.size();
int count = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] > nums[j]) {
count++;
}
}
}
return count;
}
int sortDistance(vector<int>& nums) {
vector<int> tmp = nums;
sort(tmp.begin(), tmp.end());
int n = nums.size();
int distance = 0;
for (int i = 0; i < n; i++) {
int j = 0;
for (; j < n; j++) {
if (tmp[j] == nums[i]) {
break;
}
}
distance += abs(i - j);
}
return distance;
}
int main() {
vector<int> nums = { 4, 3, 2, 1 };
int count = reverseCount(nums);
int distance = sortDistance(nums);
cout << "Reverse count: " << count << endl;
cout << "Sort distance: " << distance << endl;
return 0;
}
```
我们先来看一下`reverseCount`函数的实现。这个函数接受一个整数数组`nums`,返回这个数组的反转计数指示。我们先初始化一个计数器`count`为0,然后使用两层循环遍历数组中的所有元素对`(nums[i], nums[j])`,如果`nums[i] > nums[j]`且`i < j`,则计数器`count`加1。最后返回计数器的值即可。
接下来是`sortDistance`函数的实现。这个函数接受一个整数数组`nums`,返回这个数组排序后与原数组的距离。我们先将原数组`nums`复制到一个临时数组`tmp`中,并对`tmp`进行排序。然后遍历原数组`nums`中的每个元素`nums[i]`,找到`tmp`中与之相等的元素下标`j`,计算它们在数组中的距离`abs(i - j)`并加到距离计数器`distance`上。最后返回距离计数器的值即可。
最后在`main`函数中测试一下这两个函数的实现,输出反转计数指示和排序距离即可。
阅读全文