V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
itstudying
V2EX  ›  程序员

看到一个面试题,求解

  •  
  •   itstudying · 2019-11-30 05:58:37 +08:00 via Android · 3626 次点击
    这是一个创建于 1580 天前的主题,其中的信息可能已经有所发展或是发生改变。
    数组 a 分成 b 份形成一个二维数组(每个数组间元素个数方差最小),并且保证原数组的顺序不变,如
    [1,2,3,4,5,6,7] 分成 3 份则为,[[1,2],[3,4],[,5,6,7]] 或者[[1,2,3],[4,5],[6,7]] 两个答案都可以,只满足条件就行

    感谢大佬,最好能给套代码实现
    第 1 条附言  ·  2019-11-30 09:27:36 +08:00

    再总结下题目

    1. 数组a和分成b份,a和b均为参数
    2. 要求拆分后的二维数组中元素个数方差最小
    3. 要求拆分后的数组元素顺序保持不变
    第 2 条附言  ·  2019-11-30 09:29:15 +08:00
    拆分后的结果不唯一,满足条件即可
    第 3 条附言  ·  2019-12-01 16:59:22 +08:00
    题目是 copy 过来,原题描述不是很清晰,结贴吧。。
    17 条回复    2019-11-30 13:56:35 +08:00
    lbfeng
        1
    lbfeng  
       2019-11-30 08:49:18 +08:00
    要是分成 7 个数组方差为 0 不是更小吗
    binux
        2
    binux  
       2019-11-30 08:50:53 +08:00
    [[1,2],[3,4,5],[6,7]] 为什么不行?
    angsheng
        3
    angsheng  
       2019-11-30 08:54:12 +08:00 via Android
    每个数组间元素个数方差最小————?看不懂要求
    @lbfeng 赞同,也不知道要什么的方差最小?
    philobscur
        4
    philobscur  
       2019-11-30 09:05:41 +08:00
    @lbfeng
    @angsheng
    我猜一个数组分成 n 份的这个 n 应该是题目要求
    redeemer1001
        5
    redeemer1001  
       2019-11-30 09:07:12 +08:00
    元素个数方差最小 那直接 a/b 向下取整作为数组元素个数的基数 然后 a/b 的余数个数组多一个元素 遍历一边插入新数组
    10 行代码的事?
    redeemer1001
        6
    redeemer1001  
       2019-11-30 09:07:47 +08:00
    @redeemer1001 a/b 应该是 a.length/b
    itstudying
        7
    itstudying  
    OP
       2019-11-30 09:19:43 +08:00 via Android
    @redeemer1001 要求原数组数据顺序不变
    itstudying
        8
    itstudying  
    OP
       2019-11-30 09:21:15 +08:00 via Android
    @binux 可以,答案不唯一满足要求就行,关键是算法实现呢
    itstudying
        9
    itstudying  
    OP
       2019-11-30 09:21:56 +08:00 via Android
    @lbfeng 分成 n 份,n 是题目要求
    itstudying
        10
    itstudying  
    OP
       2019-11-30 09:22:57 +08:00 via Android
    @angsheng 题目也很清楚呀,元素个数方差最小
    fluorinedog
        11
    fluorinedog  
       2019-11-30 09:32:56 +08:00 via Android
    这题题意不是很清晰...方差最小,是指让最大方差最小,还是方差的平均值 /总和最小?
    不过两者都可以直接动态规划一波操作结束。即使允许调整顺序,也是多排个序的事。
    fluorinedog
        12
    fluorinedog  
       2019-11-30 09:34:42 +08:00 via Android
    @fluorinedog 不好意思看错题了...
    redeemer1001
        13
    redeemer1001  
       2019-11-30 09:34:52 +08:00
    @itstudying 按顺序遍历原数组插入新数组,顺序不变啊…
    我给你段 js 代码 手机打的有错见谅
    let baseL = a.length / b
    let plusOne = a.length % b
    let newArr = []
    let i = 0
    while(i < b){
    newArrBase=[]
    for(let j = 0; j < baseL; j++)
    newArrBase.push(a[i++])
    if(newArr.length < plusOne)
    newArrBase.push(a[i++])
    newArr.push(newArrBase)
    }
    itstudying
        14
    itstudying  
    OP
       2019-11-30 09:58:16 +08:00 via Android
    @redeemer1001 我也是手机,看了下代码比如 a 是[1,2,3,4,5,6,7,8] b 是 3,那么结果就是[[1,2],[3,4],[5,6,7,8]]那么各个元素个数就是 2,2,4,但其实应该是类似[[1,2,3],[4,5,6],[7,8]]这样元素个数是 3,3,2 的结果,因为 3-2 是小于 4-2 的。 或者正如#11 说的那样我题目意思理解错了?
    redeemer1001
        15
    redeemer1001  
       2019-11-30 10:00:22 +08:00
    @itstudying 我的代码跑出来的结果应该是 3 3 2
    但其实我觉得这题应该是 11 楼所说的那样……不然就太简单了
    jeffh
        16
    jeffh  
       2019-11-30 10:54:13 +08:00
    楼主题目说清楚了吗?如果个数的方差,那么直接 a.length/b 是每组的基本元素个数,其中 a.length%b 组是 a.length/b+1 个元素。代码如下,跑出来的结果是:1 2 3 ,4 5 ,6 7 ,


    ```java

    /**
    *
    * 题目:数组 a 分成 b 份形成一个二维数组(每个数组间元素个数方差最小),并且保证原数组的顺序不变,如
    * [1,2,3,4,5,6,7] 分成 3 份则为,[[1,2],[3,4],[,5,6,7]] 或者[[1,2,3],[4,5],[6,7]] 两个答案都可以,只满足条件就行
    *
    * 思路:a.length / b 为基本元素个数,a.length % b 为多出来的个数,分配到 n 组内的某几组每组一个即可
    */

    public class V2EXTest {

    public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 5, 6, 7};
    int b = 3;
    StringBuffer result = new StringBuffer();

    int index = 0;

    // a.length % b 组每组为 a.length / b + 1 个元素
    for (int i = 0; i < a.length % b; i++) {
    for (int j = 0; j < a.length / b + 1; j++) {
    result.append(a[index]);
    result.append(" ");
    index++;
    }
    result.append(",");
    }

    // 剩下的 b - a.length % b 组每组为 a.length/b 个元素
    for (int i = 0; i < b - a.length % b; i++) {
    for (int j = 0; j < a.length / b; j++) {
    result.append(a[index]);
    result.append(" ");
    index++;
    }
    result.append(",");
    }

    // 打印结果
    System.out.println(result.toString());
    }
    }
    ```
    JerryCha
        17
    JerryCha  
       2019-11-30 13:56:35 +08:00
    不知道是不是指的是方差和。是的话就是 16 楼的代码了。
    用于计算方差的平均数肯定是确定的( a/b )。
    那么平均每组的个数是 floor(a/b)。
    但是有 a%b 组个数需要加一。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1002 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 400ms · UTC 20:03 · PVG 04:03 · LAX 13:03 · JFK 16:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.