将全体数组,相加出来的值正是目的值

/*
Given an array of 2n integers, your task is to group these integers into
n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes
sum of min(ai, bi) for all i from 1 to n as large as possible.

Given an array of2nintegers, your task is to group these integers
intonpairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which
makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:
Input: [1,4,3,2]

Example 1:

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.
Note:
n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

Input:[1,4,3,2]

*/

Output:4

int arrayPairSum(int* nums, int numsSize) {

Explanation:n is 2, and the maximum sum of pairs is 4.

}

Note:

题意:两两分组,然后取每组的微小值来求和,让和最大。


nis a positive integer, which is in the range of [1, 10000].

办法1:

* 把数组排序,升序。周围的八个数作为壹组。

*
i=0开始,取nums[i*2]来相加,i=numsSize/2时截止。相加出来的值就是指标值。

* 时间复杂度O(nlogn)。

All the integers in the array will be in the range of [-10000, 10000].

办法2:

* 澳门永利备用网址,桶排序

以每种成分的值+一千0看成目录。

* 需求多大的半空中?

因为已知每一种数的限量为[-10000,10000],所以要求三千一尺寸的数组才能相对容纳这几个数。

* 具体如何排序?

* 伊始化长度为20001的数组v,每一种成分为
0。

*
遍历nums,假设每种数为i,以i+一千0当作目录,命中数组中的某一个vi(bucket),使vi++。

* 排序后,如何求和?

遍历v,在vi不为0的图景下,取一个,放三个,取出来的加至sum。最终sum为对象值。i-一千0为原数值。

* 时间复杂度O(n),使用空间换时间。


* 基础概念

*
c提供的快排的函数为qsort,陆个参数,第1参数为void*代表数组,第2个参数为要素的个数,第三个参数为种种成分的高低,最后八个参数为相比函数。相比较函数为自定义函数,情势如下:

int comp(const void* l, const void* r) {
    int lv = *((int*)l);
    int rv = *((int*)r);
    if (lv > rv) {
        return 1;
    }
    else if (lv < rv) {
        return -1;
    }
    return 0;
}

*
桶排序,是一种非相比的排序,比快排要快,但空间消耗也多。须求是,能事先分明每一个数值的限制,保持创造的数组能够容纳全数的数。1般以数的值(或运算后的值)作为数组的目录,之后依据目录也能反算出原值。

* 桶排序后的布局只怕是:

bucket_sort

*
异或的措施能够用作”抓壹放一”的招数,比如设j=一,每便j^=一,那j就会从1跟0间转移。


#include <stdio.h>
#include <stdlib.h>

int comp(const void* l, const void* r) {
   int lv = *((int*)l);
   int rv = *((int*)r);
   if (lv > rv) {
       return 1;
   }
   else if (lv < rv) {
       return -1;
   }
   return 0;
}
int arrayPairSum(int* nums, int numsSize) {
   qsort(nums, numsSize, sizeof(int), comp);    
   int i=0;
   int sum = 0;
   while (i < numsSize>>1) {
       sum += nums[i++*2]; 
   }
   return sum;
}

int main(int argc, char *argv[])
{
   int arr[] = {1, 4, 3, 2};
   printf("%d\n", arrayPairSum(arr, sizeof arr/sizeof *arr));
   return 0;
}

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
   int arrayPairSum(vector<int>& nums) {
       vector<int> buckets(20001, 0);
       for (auto i : nums) {
           buckets[i+10000] ++;    
       }
       int sum = 0;
       for (int i = 0, j=1; i < 20001;) {
           if (buckets[i] > 0) {
               if (j==1) {
                   sum += i-10000;
               }
               j^=1;
               buckets[i]--;
           }
           else {
               i ++;
           }
       }
       return sum;
   }

   int arrayPairSum2(vector<int>& nums) {
       vector<int> buckets(20001, 0);
       for (auto i : nums) {
           buckets[i+10000] ++;    
       }
       int sum = 0;
       for (int i = 0, j=1; i < 20001; i++) {
           while (buckets[i] > 0) {
               if (j==1) {
                   sum += i-10000;
               }
               j^=1;
               buckets[i]--;
           }
       }
       return sum;
   }
};

int main(int argc, const char *argv[])
{
   Solution so;
   int arr[] = {1,4,3,2};
   vector<int> v(arr, arr+sizeof arr/sizeof *arr);
   cout << so.arrayPairSum2(v) << endl;
   return 0;
}

交付1个尺寸为 贰n
的整数数组,你的职务是将那个整数分成n组,每组两个部分,并求得持有分组中较小的数的总和(那一个总和的值要硬着头皮的大)

思路:将1切数组升序排列,从下标为 0 处起首,每隔五个取一个,并求和

return sum(sorted(nums)[::2])  #sum求和 sorted升序排列 [::2]
步长为2取