精华内容
下载资源
问答
  • 某个公司的前端面试题。...问题:已知a、b两个数组,求两数组成员中最小。 js答案: 时间复杂度mn的算法实现 var A = "5 1 7 5 3 10"; var B = "4 2 9 6 3"; function getMinus(a, b) { get...
    某个公司的前端面试题。话说我也是走投无路,其他职位实在不好找,竟然回头去看前端开发。我倒不是不想做前端,只不过觉得有负我这两年的所学啊。哎!!!!

    问题:已知a、b两个数组,求两数组成员中最小的差。数组的第一位表示该数组的成员数。
    js实现:

    时间复杂度mn的算法实现
    var A = "5 1 7 5 3 10";
    var B = "4 2 9 6 3";
    
    function getMinus(a, b) {
         // get array
         a = a.split(" "), b = b.split(" ");
         // save minus
         var minus = 2147483647;
         for (i = 1; i < a.length; i++) {
             for (j = 1; j < b.length; j++) {
                 var cMinus = Math.abs(a[i] - b[j]);
                 minus = cMinus < minus ? cMinus : minus;
             }
         }
         return minus
     }
    
    时间复杂度logn的算法实现
    var A = "5 1 7 5 3 10";
    var B = "4 2 9 6 3";
    function getSortArr(a) {
        return a.split(" ").slice(1).sort(function(_a, _b) { return _a - _b });
    }
    
    function getMinusFrom2Array(a, b) {
        a = getSortArr(a), b = getSortArr(b);
        let min = Math.abs(a[0] - b[0]); // 初始差
        for (let i = 0, j = 0; i < a.length && j < b.length;) {
            let minus = a[i] - b[j];
            if (minus == 0) { // 最小输出
                return 0;
            } else {
                let cMin = Math.abs(minus);
                // console.log("cMin:" + cMin);
                min = cMin < min ? cMin : min; // 取小
                minus > 0 ? j++ : i++
            }
        }
        return min;
    }
    console.log("min minus:" + getMinusFrom2Array(A, B));
    
    展开全文
  • 交换两数组中的元素使得这两个数组的差最小 a1=A-B a2=(A-a[i]+b[j])-(B-b[j]=a[i]) =(A-B)-2*(a[i]-b[j]) =a1-2*(a[i]-b[j]) a[i]-b[j]~~(0,a1) min=a1/2; // ConsoleApplication1.cpp : 定义控制台...

    交换两数组中的元素使得这两个数组的差最小

    a1=A-B

    a2=(A-a[i]+b[j])-(B-b[j]=a[i])

    =(A-B)-2*(a[i]-b[j])

    =a1-2*(a[i]-b[j])


    a[i]-b[j]~~(0,a1) min=a1/2;


    // ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<string>
    using namespace std;
    void swap(float *A, int lenA, float *B, int lenB, float a1)
    {
    	float min_ = 10000;
    	int k1 = -1;
    	int k2 = -1;
    	for (int i = 0; i < lenA;i++)
    		for (int j = 0; j < lenB; j++){
    			int sub = abs((A[i] - B[j])-a1*1.0/2);
    
    			if (sub < min_)
    			{
    				min_ = sub;
    				k1 = i;
    				k2 = j;
    			}
    		}
    	int temp = A[k1];
    	A[k1] = B[k2];
    	B[k2] = temp;
    	
    
    }
    float FinSum(float A[], int lenA, float B[], int lenB)
    {
    	float Subsum1 = 0;
    	float Subsum2 = 0;
    	for (int i = 0; i < lenA; i++)
    	{
    		Subsum1 += A[i];
    	}
    	for (int i = 0; i < lenA; i++)
    	{
    		Subsum2 += B[i];
    	}
    	float a1 = Subsum1 - Subsum2;
    	return a1;
    }
    int main()
    {
    	float A[] = { 4,5,6 };
    	int len_a = 3;
    	float B[] = { 1,2,3};
    	int len_b = 3;
    	float a1 = 1000000;
    	float a2 = FinSum(A, len_a, B, len_b);
    	while (a2 < a1)
    	{
    		a1 = a2;
    		swap(A, len_a, B, len_b, a2);
    		a2 = FinSum(A, len_a, B, len_b);
    	}
    	return 0;
    }
    
    


    展开全文
  • 数组使数组差最小 http://hi.baidu.com/ex_dijkstra/item/1140135cf3613d16abf6d773 经常学习算法 http://www.cnblogs.com/flashbar/archive/2011/04/16/2018477.html 转载于:...

    换两个数组使两个数组和差最小

     

    http://hi.baidu.com/ex_dijkstra/item/1140135cf3613d16abf6d773

     

    经常学习算法 

    http://www.cnblogs.com/flashbar/archive/2011/04/16/2018477.html

     

     

    转载于:https://www.cnblogs.com/luofeng225/p/3684362.html

    展开全文
  • 数组最小差

    2015-05-15 14:26:48
    给定个整数数组(第一个是数组 A,第二个是数组 B),在数组 A 中取 A[i],数组 B 中取 B[j],A[i] 和 B[j]两者的越小越好(|A[i] - B[j]|)。返回最小差。 样例 给定数组 A = [3,4,6,7], B = [2,3,8,9],...
  • 要求通过交换a,b数组的元素,使得数组a的和与数组b的和的差最小。   这个题目网上很多博客给出的一种解法都是错的,他们的思路是每次交换一对数据,如果交换能使得差变小就交换,否则就不交换。这个解法简单...

    题目来源于传说中的华为面试题:

    有两个长度都为 n 的数组,分别为 a,b。数组元素类型为整型,值任意且无序。要求通过交换 a,b 数组的元素,使得数组 a 的和与数组 b 的和的差最小。

      这个题目网上很多博客给出的一种解法都是错的,他们的思路是每次交换一对数据,如果交换能使得差变小就交换,否则就不交换。这个解法简单直观,其实本来目的就是穷举。可是本题却存在这种情况,即找不到任何一对数据的交换使得差变小(这也是上面算法的停止条件),但存在同时交换多对数据使得差变小的情况。
      网上的这个主流解法错就错在没有考虑同时交换多对数据的情况,下面我将介绍本题的一种使用动态规划的解法。

    使用动态规划求解

      把原问题看作:有 2n 个非负整数(题目给的条件是值任意,后面我会介绍转换方法),和为 S2nS_{2n},我们要在 2n 个数中选出 n 个数,使得这 n 个数的和 SnS_{n} 满足:min(S2n2Sn)min(\frac{S_{2n}}{2}-S_{n})

    描述为背包问题就是:

    从 2n 件物品中选出 n 件物品,放入容量为 S2n2\frac{S_{2n}}{2} 的背包中,使得背包装的东西尽可能的多。(把第 i 个元素的值,既看作第 i 件物品的开销也看作第 i 件物品的价值)

      这其实是一个在普通的 0-1 背包上多加了一个限制条件的背包问题,多加了放入背包物品的数量的限制。
      我们可以在原来的基础上增加一维以满足新的限制。

    状态转移方程:

      设 f[i][j][v] 表示前 i 件中选出 j(j <= i)件放入容量为 v 的背包中所能获得的最大价值,a[i] 为第 i 个元素的值。
    f[i][j][v]=max{f[i1][j][v],f[i1][j1][va[i]]+a[i]}f[i][j][v]=max\{f[i-1][j][v],f[i-1][j-1][v-a[i]]+a[i]\}
      空间优化后为:
    f[j][v]=max{f[j][v],f[j1][va[i]]+a[i]}f[j][v]=max\{f[j][v],f[j-1][v-a[i]]+a[i]\}

    数据预处理(填坑)

    本题满足平移不变性,即所有元素加上或减去一个整数,两数组和的差不变。

      我们可以利用这个性质,将所有元素都减去 2n 个元素中的最小值。

    • 好处一:如果 2n 个元素中存在负数,则最小值必然是负数,减去这个负数,可以使得所有元素非负,进而可以使用背包求解。
    • 好处二:如果 2n 个元素本来就是正数,则全部都减一个最小值,可以减小背包容量,从而降低求解的空间复杂度。

    参考代码:

    #include<stdio.h>
    #define LEN 8
    int select(int *a) {
    	int i, j, v;
    	int imax = LEN;
    	int jmax = imax / 2;
    	int suma = 0;
        // 求和
    	for (i = 0; i < LEN; i++){
    		suma += a[i];
    	}
    	int vmax = suma / 2;
    	int dp[jmax + 1][vmax + 1], sel[jmax + 1][vmax + 1];
        // 初始化
    	for (j = 0; j <= jmax; j++){
    		for (v = 0; v <= vmax; v++){
    			if (j == 0){
    				dp[j][v] = 0;
    			}
    			else{
    				dp[j][v] = -1;
    			}
    			sel[j][v] = 0;
    		}
    	}
        // i 从 1 开始而不是从 0,是为了避免 j-1<0 越数组下界的情况
    	for (i = 1; i <= imax; i++){
            // 因为 dp 数组减少了一维,又因为物品不能重复放入,所以要从后向前遍历更新
    		for (j = i > jmax ? jmax : i; j >= 1; j--){
    			for (v = a[i - 1]; v <= vmax; v++){
    				if (dp[j - 1][v - a[i - 1]] < 0) continue;
    				else if (dp[j - 1][v - a[i - 1]] + a[i - 1] > dp[j][v]){
    					dp[j][v] = dp[j - 1][v - a[i - 1]] + a[i - 1];
                        // 记录此时放入背包中的物品
    					sel[j][v] = sel[j - 1][v - a[i - 1]] | (1 << (i - 1));
    				}
    			}
    		}
    	}
    	printf("分配后两数组和的差为:%d", suma - 2*dp[jmax][vmax]);
    	return sel[jmax][vmax];
    }
    
    void outputGroup(int *a, int sel) {
    	printf("\n数组a的元素分别为:");
    	for (int i = 0; i < LEN; i++){
    		if (sel & (1 << i)){
    			printf("%d ", a[i]);
    		}
    	}
    	putchar('\n');
    }
    
    int main() {
        // 测试数据
    	int arry[LEN] = { 54, -58, 22, 49, 64, -21, 33, 90 };
    	int a[LEN];
    	for (int i = 0; i < LEN; i++){
    		a[i] = arry[i];
    	}
        // 下面对所有数据进行预处理,减去最小值
    	int min = a[0];
    	for (int i = 1; i < LEN; i++){
    		if (a[i] < min){
    			min = a[i];
    		}
    	}
    	for (int i = 0; i < LEN; i++){
    		a[i] -= min;
    	}
        // 输出选出的 a 数组,剩下元素属于 b 数组
    	outputGroup(arry, select(a));
    	return 0;
    }
    

    代码运行结果为:
    运行结果

    展开全文
  • 个升序数组最小元素

    千次阅读 2016-03-24 16:51:34
    解题思路:首先想到的是暴力解法,即内外双循环,逐一拿数组中的元素作,取最小的min,但这样做的时间复杂度达到了O(m*n)。所以想优化解法,先上代码再解析吧: int GetMinArraySubtraction(int A[], int lenA, ...
  • 问题:给定个整数数组a和b,计算具有最小差绝对值的一对数值(每个数组中取一个值),并返回该对数值的 解题思路 先排序,然后设定返回值为最大,用双指针求得结果。 代码 class Solution { public: int ...
  • 数组-最小差-中等

    2018-06-21 19:04:38
    描述给定个整数数组(第一个是数组 A,第二个是数组 B),在数组 A 中取 A[i],数组 B 中取 B[j],A[i] 和 B[j]两者的越小越好(|A[i] - B[j]|)。返回最小差。您在真实的面试中是否遇到过这个题? 是样例给定数...
  • 要求:通过交换a,b 中的元素,使[序列a 元素的和]与[序列b 元素的和]之间的差最小。 例如: var a=[100,99,98,1,2, 3]; var b=[1, 2, 3, 4,5,40]; 假设序列a,b中元素的和为sum_a和sum_b。假设aa和bb分别为序列a...
  • 要求:通过交换a,b中的元素,使数组a元素的和与数组b元素的和之间的差最小 当前数组a和数组b的和之差为 A = sum(a) - sum(b) a的第i个元素和b的第j个元素交换后,a和b的和之差为 A' = sum(a) - a[i] + b[j] - ...
  • 调整数组使得差最小

    2019-10-20 13:04:21
    调整数组使差最小 Description 有个序列 a,b,大小都为 n,序列元素的值任意整数,无序; 要求:通过交换 a,b 中的元素,使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。 Input 输入第一行为用例个数, 每个...
  • 今天又看见了这个题目,好像上次是李灾跟我说腾讯面他的时候问了这个问题的。... 要求:通过交换a,b中的元素,使[数组a元素的和]与[数组b元素的和]之间的差最小。 */ /*  求解思路:  当前数组a和数组
  • 将一个数组分为数组,使数组和的差最小 */ public class SplitArray{ public int diff(int[] array){ int sum = 0; for(int i=0; i<array.length; i++){ sum += array[i]; } ...
  • 要求:通过交换 a,b 中的元素,使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。 Input: 输入第一行为用例个数, 每个测试用例输入为行,分别为数组,每个值用空格隔开。 Output: 输出变化之后的...
  • 调整数组使差最小 Description 有个序列 a,b,大小都为 n,序列元素的值任意整数,无序; 要求:通过交换 a,b 中的元素,使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。 Input 输入第一行为用例个数, 每个...
  • 所谓能交换,就是交换过后,两数组和之比当前小。我设想了一个迭代算法,就是将当前的交换尝试,重复,直到没有一个值再能交换为止! 代码如下: 1 a = [170, 100, 5, 4, 3, 2, 1] 2 b = [101, 100, 15, 14...
  • 个子数组和的差最小

    千次阅读 2018-06-23 02:29:32
    给定一个数组,将其分成部分,使得这部分数组的和的差最小。本质上是01背包问题。 #include&lt;iostream&gt; #include&lt;vector&gt; #include&lt;algorithm&gt; using namespace std...
  • /* *有数组a[n]和b[n],都是无序的 ...*总和之差最小 */ #include #define SIZE 3 int sumb (int m[], int n) /*计算数组元素之和*/ { int i; int sum = 0; for (i = 0; i ; i++) sum += m[i];
  • 交换数组使数组和的差最小 题目描述 Description 有个序列 a,b,大小都为 n,序列元素的值任意整数,无序; 要求:通过交换 a,b 中的元素,使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。 Input ...
  • 旋转数组最小数字

    2021-03-25 19:27:40
    设置前后指针,通过更新指针,直到个位置只为1的时候,第二个指针所指向的位置就是最小元素。 需要注意的是个指针指向的位置的元素一样时,就需要遍历了,如{1, 1, 1, 0, 1} def min_num(nums):
  • 要求:通过交换a,b中的元素,使数组a元素的和与数组b元素的和之间的差最小  很久之前就看到过这条题目,思路是有的,也没看网上其他人是怎么解的:  1. A,B需要分别建最大堆(复杂度2N),维护各自的和...
  • package aAndb_change_to_abs_min;...要求:通过交换a,b 中的元素,使[序列a 元素的和]与[序列b 元素的和]之间的差最小。 例如: var a=[100,99,98,1,2, 3]; var b=[1, 2, 3, 4,5,40]; * */ public class Solution {
  • 8、调整数组使差最小

    2019-01-08 15:04:25
    8、调整数组使差最小 Description 有个序列 a,b,大小都为 n,序列元素的值任意整数,无序; 要求:通过交换 a,b 中的元素,使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。 Input 输入为行,分别为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,039
精华内容 415
关键字:

两数组差最小