华为面试题
32.
有两个序列a,b,大小都为n,序列元素的值任意整数,无序;
要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
求解思路:
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后,a和b的和之差为
A' = sum(a) - a[i] + b[j] - (sum(b) - b[j] + a[i])
= sum(a) - sum(b) - 2 (a[i] - b[j])
= A - 2 (a[i] - b[j])
设x = a[i] - b[j]
|A| - |A'| = |A| - |A-2x|
|A'|= |A-2x|
假设A > 0,
当x 在 (0,A)之间时,做这样的交换才能使得交换后的a和b的和之差变小,x越接近A/2效果越好,
如果找不到在(0,A)之间的x,则当前的a和b就是答案。
所以算法大概如下:
在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j,交换相应的i和j元素,重新计算A后,重复前面的步骤直至找不到(0,A)之间的x为止。
C# codes as below:
using System;
namespace ConsoleApp
{
class RunClass
{
static void Main()
{
int[] array1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 90, 0, 0, 100 };
int[] array2 = { -1, -2, -100, -3, 99, -222, -2, -3, -5, -88, 11, 12, 13 };
new Helper().BalanceArray(ref array1, ref array2);
foreach (int i in array1)
{
Console.Write("{0} ", i);
}
Console.WriteLine();
foreach (int i in array2)
{
Console.Write("{0} ", i);
}
Console.ReadLine();
}
}
class Helper
{
public void BalanceArray(ref int[] array1, ref int[] array2)
{
if (array1.Length != array2.Length)
return;
if (Sum(array1) < Sum(array2))
{
int[] array = array1;
array1 = array2;
array2 = array;
}
bool ifCycle = true;
int length = array1.Length;
while (ifCycle)
{
ifCycle = false;
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length; j++)
{
int itemValue = array1[i] - array2[j];
int sumValue = Sum(array1) - Sum(array2);
if (itemValue < sumValue && itemValue > 0)
{
ifCycle = true;
int item = array1[i];
array1[i] = array2[j];
array2[j] = item;
}
}
}
}
}
private int Sum(int[] array)
{
int sum = 0;
for (int i = 0; i < array.Length; i++)
{
sum += array[i];
}
return sum;
}
}
}
分享到:
相关推荐
有两个数组a,b,大小都为n,数组元素的值任意,无序 //要求:通过交换a,b中的元素,使数组a的元素之和与数组b的元素之和之间//的差最小?
优先队列求无序整数序列中第k小的元素.cpp
有两个序列a,b,大小都为n,序列元素的值任意整数,无序; 要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。 例如: var a=[100,99,98,1,2, 3]; var b=[1, 2, 3, 4,5,40]; 求解思路: ...
给定一个无序的整数序列,以及一个目标序号 n . 将整数序列的元素按照出现次数由高到低划入不同等级的集合,出现次数同样多的划入一个集合。取第 n个(n从 1 开始)集合,即出现次数第 n 多(并列的只占一个排名)的...
给定一个整数数组,其中元素的取值范围为0到10000,求其中出现次数最多的数
A) 定义了一个名为a的一维数组 B) a数组有3个元素 C) a数组的下标为1~3 D)数组中的每个元素是整型 6.若a和b均是整型变量并已正确赋值,正确的switch语句是( )。 A) switch(a+b); B) switch( a+b*3.0 ...
北邮的大一第一学期的计导课程的红皮书部分习题作业源代码
假设两个顺序线性表La和Lb分别表示两个集合A和B,如何实现A=A ∩B ? 实验2:单链表基本操作 一、 实验目的 1. 学会定义单链表的结点类型,实现对单链表的一些基本操作和具体的函数定义,了解并掌握单链表的类定义...
6.数据结构中评价算法的两个重要指标是(时间复杂度和空间复杂度) 【北京理工大学 2001 七、1(2分)】 7. 数据结构是研讨数据的_(1)物理结构_和_(2)逻辑结构 _,以及它们之间的相互关系,并对与这种结构定义...
初始时,dp 数组中的所有元素都设为 1,因为每个单独的元素本身就是一个长度为 1 的上升子序列。 动态规划:遍历输入数组 nums,对于每个元素 nums[i],再遍历它之前的所有元素 nums[j](其中 j ),如果 nums[i] >...
简单插入排序思想,将一个无序的数组,想象成由两部分组成,一部分为有序列,一部分为无序列,初始时,有序列为数组第一个元素,无序列为第一个元素之后的元素组成。每次从无序列中取第一个数插入到有序列中,有序列...
例如,对图1-1中的二叉树进行前序遍历的结果(或称为该二叉树的前序序列)为:A,B,D,E,C,F。 (2)中序遍历 先遍历左子树、然后访问根结点,最后遍历右子树;并且,在遍历左、右子树时,仍然先遍历左子树,然后...
D. *建立函数create:根据一维数组a[n]建立一个单链表,使单链表中各元素的次序与a[n]中各元素的次序相同,要求该程序的时间复杂度为O(n)。 E. *整理函数tideup:在非递减有序的单链表中删除值相同的多余...
字典(dict)是一种无序的、可变的序列,它的元素以“键值对(key-value)”的形式存储。 字典的每个键值 key=>value 对用冒号 : 分割,每个对之间用逗号(,)分割,整个字典包括在花括号 {} 中 ,格式如下所示: d = {...
学习算法时一个求第k小元素的小例子。内含代码和输入文件。很好用哦!
(2)从文件A读入30个无序整数,建立一个递增的单链表A并输出,从文件B读入30个无序整数,建立一个递增的单链表B并输出,在A中求递增的并集。 (3)从文件读入30个学生成绩(0-100之间),建立一个双向循环链表并...
字典中的每个元素都是一个键值对,包含:“键对象”和“值对象” 键是任意不可变数据,如:整数、浮点数、字符串、元组。 1.1 字典的创建 1.通过[}, dict()来创建字典 a={‘name’:'ju’,'age'=18}#创建字典a a=...
初始化两个指针 left 和 right 分别指向当前连续序列的起始和结束位置,同时初始化最长连续序列长度 maxLength 为0。 遍历数组 nums,对于每个元素 num: 如果 num-1 不在哈希表中,则移动右指针 right 并更新哈希表...
29.选择排序的思想是,将数据序列划分为两个子列,一个子列是排好序的,另一个是尚未排序的。现若想将数据序列由小到大排序,则每次放到有序子列尾部位置的元素,应从无序序列中选择( )。 A)最大的 B)最小的 C)任意的...
最长上升子序列问题可以这样定义:给定一个无序的整数数组,任务是找到该数组中一个最长的子序列,使得这个子序列中的元素从左到右是严格递增的。这里的“子序列”是指从原数组中挑选出的一些元素,它们保持原序列中...