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

青旅半醒 2022-04-16 06:09 184阅读 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 条评论，184人围观）

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

相关阅读

相关 [每日一道小算法（二十四）] [二分查找]旋转数组的最小数字（剑指offer习题）

前言：这是一道二分查找法变形的题型，很有意义，值得学习。题目类型把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数

ゞ浴缸里的玫瑰/ 2023年07月04日 15:55/ 0 赞/ 1 阅读

相关 530. 二叉搜索树的最小绝对差

> 给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。 > > ![watermark_type_ZmFuZ3poZW5naGVpdGk_sh

超、凢脫俗/ 2022年10月08日 00:50/ 0 赞/ 125 阅读

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

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

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

相关二维数组和指针

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关 Java开发笔记（二十一）二维数组的扩展

前面介绍的数组容纳的是一串数字，仿佛一根线把这组数字串了起来，故而它只是一维数组。一维数组用来表示简单的数列尚可，要是表达复杂的平面坐标系，那就力不从心了。由于平面坐标系存在水

墨蓝/ 2022年04月18日 03:35/ 0 赞/ 202 阅读

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

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

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