算法二十二：数组和之间差最小

青旅半醒 2022-04-16 06:09 174阅读 0赞

有两个序列a,b，大小都为n,序列元素的值任意整数，无序；

要求：通过交换a,b中的元素，使\[序列a元素的和\]与\[序列b元素的和\]之间的差最小。

例如:

var a=\[100,99,98,1,2, 3\];

var b=\[1, 2, 3, 4,5,40\];

分析：要是序列的和之差最小，考虑将两个序列组合成一个序列1，对序列求和sum，选取一个数组，使得这个数组的和最接近sum/2，对合成序列1求和，然后取均值，再进行选取那些与这个均值最接近的序列1中的数，放入序列a中，这样可以使得数组和最近进sum/2。

代码：

MinMinus.h

\#ifndef MINMINUS\_CPP

\#define MINMINUS\_CPP

\#include< iostream>;

\#include< vector>;

\#include <math.h>

using namespace std;

void MinMinus(int n,int c\[\]);

int extractmin(vector<double> ivec,vector<bool> visited);

\#endif

MinMinus.cpp

\#include "MinMinus.h"

void MinMinus(int n,int c\[\])\{

vector<int> a,b;

int sum=0;

vector<double> ivec;

vector<bool> visited;

int k;

int index=0;

double ave;

for(int i=0;i<2\*n;i++)\{

sum += c\[i\];

\}

ave = (double)sum/(2\*n);

for(int i=0;i<2\*n;i++)\{

ivec.push\_back(c\[i\]-ave);

visited.push\_back(false);

\}

for(int i=0;i<n;i++)\{

k = extractmin(ivec,visited);

a.push\_back(c\[k\]);

visited\[k\] = true;

\}

for(int i=0;i<2\*n;i++)\{

if(visited\[i\]==false)\{

b.push\_back(c\[i\]);

visited\[i\] = true;

\}

\}

for(int i=0;i<n;i++)\{

cout<<a\[i\]<<"\\t";

\}

cout<<endl;

for(int i=0;i<n;i++)\{

cout<<b\[i\]<<"\\t";

\}

\}

int extractmin(vector<double> ivec,vector<bool> visited)\{

int k;

int i;

for(i=0;(i<ivec.size())&&(visited\[i\]==true);i++);

k = i;

for(;i<ivec.size();i++)\{

if((fabs(ivec\[i\])<fabs(ivec\[k\]))&&(visited\[i\]==false))\{

k = i;

\}

\}

return k;

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关二维数组的最小路径和问题

> 给定一个只含非负整数的`m ∗ n`网格，找到一条从左上角到右下角的可以使数字和最小的路径。暴力解法（超时）[\][Link 1] 定义递归函数 int

朴灿烈づ我的快乐病毒、/ 2024年04月06日 11:21/ 0 赞/ 29 阅读

相关二. python数组和列表

class Array(object): def __init__(self, size=32): self._size=size self._item=[None]s

水深无声/ 2023年08月17日 16:33/ 0 赞/ 107 阅读

相关异方差性和加权最小二乘法详解

加权最小二乘是对原模型进行加权，是该模型成为一个新的不存在异方差性的模型，然后对该新模型使用普通最小二乘法估计其参数进行优化。异方差性的解释：随机误差的方差不全相等。异方

傷城~/ 2023年07月14日 05:26/ 0 赞/ 31 阅读

相关二十世纪最伟大的十大算法

发明十大算法的其中几位算法大师 ![640?wx\_fmt=png&wxfrom=5&wx\_lazy=1][640_wx_fmt_png_wxfrom_5_wx_lazy_

今天药忘吃喽~/ 2022年09月03日 15:29/ 0 赞/ 200 阅读

相关二维数组和指针

<table style="font-family:simsun; margin:0px; padding:0px"> <tbody> <tr> <td st

桃扇骨/ 2022年08月04日 21:28/ 0 赞/ 203 阅读

相关算法-旋转数组的最小数字

题目输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组\{3,4,5,1,2\}为数组\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。旋

古城微笑少年丶/ 2022年06月10日 01:44/ 0 赞/ 152 阅读

相关算法二十九：最大间隙

问题描述给定长度为 n 的数组 a，其中每个元素都为 \[0,2^k) 之间的整数，请求出它们在实数轴上相邻两个数之间的最大值（即maxGap）。由于 n 可能很大

悠悠/ 2022年05月21日 09:07/ 0 赞/ 166 阅读

相关算法二十六：邓老师数

问题描述众所周知，大于 1 的自然数中，除了 1 与其本身外不再有其他因数的数称作质数（素数）。对于大于 1 的不是质数的自然数，我们又称作合数。参加了邓老师算

た入场券/ 2022年05月21日 08:12/ 0 赞/ 135 阅读

相关细数二十世纪最伟大的十大算法

参考论文： The Best of the 20th Century: Editors Name Top 10 Algorithms。 By Barry A.

谁借莪１个温暖的怀抱￠/ 2022年05月16日 08:13/ 0 赞/ 184 阅读

相关算法二十二：数组和之间差最小

有两个序列a,b，大小都为n,序列元素的值任意整数，无序；要求：通过交换a,b中的元素，使\[序列a元素的和\]与\[序列b元素的和\]之间的差最小。例如: var

青旅半醒/ 2022年04月16日 06:09/ 0 赞/ 175 阅读