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

/*
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/二时截止。相加出来的值正是目的值。

* 时间复杂度O(nlogn)。

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

办法2:

* 桶排序

以各样成分的值+一千0作为目录。

* 须要多大的半空中?

因为已知每一个数的限定为[-10000,10000],所以须求30001长度的数组本领相对容纳这个数。

* 具体什么排序?

* 开头化长度为两千一的数组v,各个成分为
0。

*
遍历nums,固然种种数为i,以i+10000当做目录,命中数组中的某贰个vi(bucket),使vi++。

* 排序后,如何求和?

遍历v,在vi不为0的境况下,取3个,放三个,收取来的加至sum。最终sum为对象值。i-10000为原数值。

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


* 基础概念

*
c提供的快排的函数为qsort,八个参数,第1参数为void*代表数组,第3个参数为成分的个数,第四个参数为各种成分的大小,最终3个参数为相比函数。比较函数为自定义函数,格局如下:

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组,每组三个部分,并求得装有分组中十分小的数的总和(那一个总和的值要尽量的大)

思路:将全部数组升序排列,从下标为 0 处初叶,每隔多少个取一个,并求和

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

相关文章

网站地图xml地图