100元现金奖赏征求算法

悠悠然然 发布于 2017/12/26 23:11
阅读 3K+
收藏 6

有10个列表,里面放着整数,并且从小到大排序。

要求:编程语言必须为java,有这么一个list数组其长度为10。其实会给这10个数组填充了一些整数,且均按照从小到大排序。

请完成函数getOrderList,输入参数为开始位置startPosition,返回值为每个列表中的开始位置,这些位置满足:

1.如果startPosition<=0,则开始位置均为0

2.如果startPosition>所有列表长度之和,则开始位置均为各自的列表长度

3.其他情况下startPosition=各列表开始位置之和,且任意一个数组从其对应开始位置后面的数字都不小于其他数组各自开始位置前的数字。

比如下面就是10个列表,总长度表示列表中数字的多少。黄蓝分割点就是每个列表中的开始位置,所有列表开始位置相加的和等于startPosition,且所有蓝色区域的数字均大于等于黄色部分的数字。

本质等价于:从10个各自有序列表取n个有序数的时候,返回每个列表取到了第几个数。之所以没有这么描述是怕影响实现算法。

 

获奖条件:

1.功能首先要正确

2.同样功能正确,效率高者获胜

3.功能正确效率也差不多(10%之内),提交早者获胜。

4.暴力(低效)算法无效。

如果题目有问题,请回复,会马上给予解释或完善。

 

 

加载中
0
悠悠然然
悠悠然然

已经结贴。

花费时间:17ms
起始位置:9736 9745 9740 9747 9796 
当前位置:316 318 318 318 318 
前序位置:319 319 319 320 319 

在50000个数据的情况下,用17ms找到合适的位置,效果不错,100红包已发,本帖结束。

1
vishva
vishva

我大体明白楼主的意思了

大约就是这么一个东西

    /**
     * 存放有序不定长数组的list
     */

    private List<int[]> orderNoList;

    /**
     *如果按照某种顺序从list中取出一定数量的数字的话
     *param acquiredNoSum 所取得数字的总数量
     *return eachAcquiredNoCount 各自所取数字的数量
     */

    public int[] geteachAcquiredNoCount (int acquiredNoSum){
        //        todo
        return new int[10] ; 
    }

不过你没有说明是按照什么样的顺序取得数字,但你强调了取出有序数我暂且按照以下算法从数组中取数

假定a为下一个被取出的数,a满足以下条件

1,a存在于list orderNoList中的一个数组中

2,假定有序数组b存放有所有已被取出的数并且c表示max(b),

则a=min(orderNoListv中未取数)(多个数组中的最小数字相等时取靠前的一个)

并且a>=c

 

可以将具体的取数算法封装起来,替换成自己需要的算法

具体算法为

用一个int 数组当作游标

另一个int数组存放待比较的数

通过游标得到待比较数组

 

得出待比较数组中最小的数对应数组序号以及,相应游标加1,从相应数组取出一个数更新待比较数组,,重复这一步直到所有游标之和等于需取出数的数量

返回游标数组

算法时间复杂度为O(n)与从n个数中找出最小的数是一个数量级,我觉得不可能还有比这更高效的算法了

 

 

悠悠然然
悠悠然然
谢谢回复,你的算法有解,但是还不够高效:)
0
悠悠然然
悠悠然然

@红薯 直接粘贴上传还是不支持,chrome和safari都不行。

0
乌龟壳
乌龟壳
【返回值为每个列表长度的长度为10的整数数组】是什么意思
悠悠然然
悠悠然然
已调整说明
0
W
WeiYongxin

我先回去学学语文~

 

悠悠然然
悠悠然然
已调整说明,请在看看?
0
太黑_thj
太黑_thj

看完这个需求后,我也觉得我该回去重新读一遍新华字典了

0
梅开源
梅开源

任意一个数组从其对应位置开始的数字都不大于其他数组对应位置前的数字

那么是都相等咯?

0
紅顏為君笑
紅顏為君笑

语文老师的棺材板要按不住了

悠悠然然
悠悠然然
这个问题确实比较难描述,主要看图和标红了的部分吧
0
tcxu
tcxu

命题需要重新措辞,以便确切地表明具体场景。如开场白是否改为:

用JAVA语言完成方法getOrderLIst 的代码填写任务。如静态代码块所示,现已拥有一个长度为10的数组 list。  它的每个元素都是一个已经按照从小到大排序好的 List<Integer>实体。 …

悠悠然然
悠悠然然
回复@tcxu : 非常好,如果看懂了,来一个普通人懂得版本。
0
g
gm100861

真心读不懂,也不知道"分界索引值"是个什么东西,怎么算出来的.

返回顶部
顶部