算法题（K个最大偶数和奇数数组元素之和之间的差） _数据结构

给定一个数组arr[]和一个数字K，任务是找到K个最大的偶数和奇数数组元素之和的绝对差。
注意:至少有K个偶数和奇数元素分别出现在数组中。
例子：

输入arr [] = {1, 2, 3, 4, 5, 6}, K = 2
输出：2
说明：
2个最大偶数为6、4。总和为6 + 4 =10。
2个最大奇数数字是5、3。总和是5 + 3 =8。
差= 10 – 8 =2。
输入arr [] = {1、8、4、5、6、3}, K = 3
输出：4
说明：
3个最大偶数是8、6、4。总和是8 + 6 + 4 =18。
3个最大奇数是5、3、1。总和是5 + 3 + 1 =9。
差= 18 – 9 = 9。

简单方法:最简单的方法是遍历数组找到K个最大的偶数和K个最大的奇数，然后打印得到的K个最大的偶数和奇数元素之和之间的绝对差。
时间复杂度：O(N * K)
辅助空间：O(1)
高效方法：为了优化上述方法, 想法是使用将数组分为奇数和偶数然后将数组按降序分为两部分, 分别包含偶数和奇数。请按照以下步骤解决问题：

将给定数组中的偶数和奇数分开并从奇数开始存储索引。
让索引从奇数开始?。对范围内的数字进行排序[0, K – 1]和[K, N – 1]以降序排列。
第一个的总和?从数组开头到奇数开头的数字是第一个和最大K数组中的偶数和奇数。
打印上一步中计算出的总和之间的绝对差作为结果。

下面是上述方法的实现：
C ++

//C++ program for the above approach#include < bits/stdc++.h> using namespace std; //Function to find the absolute //difference between sum of first K //maximum even and odd numbers void evenOddDiff( int a[], int n, int k) { //Stores index from where odd //number starts int j = -1; //Segregate even and odd number for ( int i = 0; i < n; i++) {//If current element is even if (a[i] % 2 == 0) { j++; swap(a[i], a[j]); } }j++; //Sort in decreasing order even part sort(a, a + j, greater< int> ()); //Sort in decreasing order odd part sort(a + j, a + n, greater< int> ()); int evenSum = 0, oddSum = 0; //Calculate sum of k //maximum even number for ( int i = 0; i < k; i++) { evenSum += a[i]; }//Calculate sum of k //maximum odd number for ( int i = j; i < (j + k); i++) { oddSum += a[i]; }//Print the absolute difference cout < < abs (evenSum - oddSum); }//Driver Code int main() { //Given array arr[] int arr[] = { 1, 8, 3, 4, 5 }; //Size of array int N = sizeof (arr) /sizeof (arr[0]); int K = 2; //Function Call evenOddDiff(arr, N, K); return 0; }

输出如下：