leetcode算法题3:分组,让每个组的极端小者,相加后和最可怜。想知道桶排序是怎么样的也?LeetCode 1. Two Sum

/*
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 of integers, return indices of the two numbers such that
they add up to a specific target.
You may assume that each input would have exactly one solution, and you
may not use the same element twice.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1]
= 2 + 7 = 9,return [0,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].

翻译:

受一定一个平头再三组,返回两独数的目,使它们的与为一个对象价。
若可使每个输入还单来一个答案,且一个要素只能使同一不成。

*/

Solution 1: 双重循环

下重复循环,遍历所有的景况,时间复杂度为 O(n^2) 。
每当内层的循环中,索引从 i + 1 开始。

//Kotlin
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        for (i in 0..(nums.size - 1))
            for (j in (i + 1)..(nums.size - 1))
                if (nums[i] + nums[j] == target)
                    return intArrayOf(i, j)
        return intArrayOf()
    }
}

int arrayPairSum(int* nums, int numsSize) {

Solution 1.1:

本着端的代码做有小的优化,在率先重复循环中计算另一个再三的价值,可以减加减计算次数。时间复杂度仍为
O(n^2) 。

//Kotlin
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        for (i in 0..(nums.size - 1)) {
            val remain = target - nums[i]
            for (j in (i + 1)..(nums.size - 1))
                if (nums[j] == remain)
                    return intArrayOf(i, j)
        }
        return intArrayOf()
    }
}

}

Solution 2:

旁一样栽方法是对于曾经排序的勤组,从零星端向中查找。
拿数组从小至很排序,两个目录分别吗数组的第一只与结尾一个元素,如果个别个价的超目标价,第二只寻引减1,反的第一个索引加1,直到片单数的和也目标价。

//Kotlin
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val ns = nums.mapIndexed { index, i -> Pair(index, i) }.sortedBy { p -> p.second }
        var a = 0
        var b = ns.size - 1
        while (a != b) {
            val sum = ns[a].second + ns[b].second
            when {
                sum == target -> return intArrayOf(ns[a].first, ns[b].first)
                sum > target -> b--
                sum < target -> a++
            }
        }
        return intArrayOf()
    }
}

题意:两个别分开组,然后抱每组的无限小值来求和,让与最好充分。


Solution 3: 使用HashMap

遍历数组,每个循环中,尝试当HashMap中检索第二单数的盼望值,如果找到,返回结果,否则把当下数字放入HashMap,用于下次查找。时间复杂度为O(n)。

//Kotlin
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = HashMap<Int, Int>()
        nums.forEachIndexed { index, i ->
            val a = map.get(target - i)
            if (a != null) {
                return intArrayOf(a, index)
            }
            map.put(i, index)
        }
        return intArrayOf()
    }
}

办法1:

* 把数组排序,升序。邻近的鲜个数作为同组。

*
i=0开始,取nums[i*2]来相加,i=numsSize/2时结束。相加出来的值就是目标价。

* 时间复杂度O(nlogn)。

办法2:

* 桶排序

为每个元素的值+10000看成目录。

* 需要多坏之上空?

因为就解每个数之克为[-10000,10000],所以需要20001长的数组才能够绝对容纳这些往往。

* 具体哪些排序?

* 初始化长度也20001之再三组v,每个元素呢
0。

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

* 排序后,如何告与?

凡事历v,在vi不为0的情状下,取一个,放一个,取下的加至sum。最终sum为对象价。i-10000为本数值。

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


* 基础概念

*
c提供的快排的函数为qsort,4只参数,第1参数为void*表示数组,第2只参数为要素的个数,第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;
}

*
桶排序,是同一栽不比的排序,比快破要抢,但空间消耗也差不多。要求是,能事先确定每个数值的限定,保持创建的数组能够容纳有的累。一般以数的价(或运算后的价值)作为数组的目录,之后因目录也克反算出原值。

* 桶排序后底构造或是:

bucket_sort

*
异或的法子可以看作”抓一放大平”的手腕,比如设j=1,每次j^=1,那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;
}

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注