算法题：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;
}

输出如下：

4

时间复杂度：O(N * log N + K)

辅助空间：O(1)