有一个一维数组，值域为[0，10]，如array[10]={0,0,0,2,5,0,0,4,3,0};
现在的要求是，控制数组的非0元素的数量，比如要求非0元素最多为2个，那么上面这个数组的非0元素个数4就超过了2个，于是要随机选择2个非0元素赋值为0。现在的问题是怎么样的算法能够用最短的时间内解决问题。

一个简单的办法是
modify_num=0; //被修改的元素个数，在上例中应该上限为2
while(modify_num<2)
{
pos=rand(10); //随机产生一个拟修改的元素位置
if(array[pos]!=0) //只有非0元素才需要修改
{
array[pos]=0;
modify_num++;
}
}

这种算法会无谓浪费很多由于随机指定的元素已经是0而不需要修改的时间，不知道有没有更好的办法。

没人帮忙吗？自己顶下先！

我实在是搞不懂你的程序和你说的要求有什么关联,更搞不懂为什么要来个随即函数
再你的程序中貌似你已经知道要修改的个数,这个个数你是怎么知道的?那你为什么不在求这个个数的时候不把那些非零数收集起来呢?

谢谢关注，使用随机数是算法要求，因为我写的是非确定性搜索算法。程序需求没法改的，不然需要打破理论限制，现在希望在理论即定的前提下提高程序效率呵

这个效率问题是可能存在重复选择0,提高效率就得把这个重复工作尽量消除.

说个做法(不一定正确,自己考虑下,看行不行)

重新记录非0值存放一数组里面,一层元素值表示原数组的位置.第二层表示原数组的值,以便修改为0的.
然后直接随机选择.

额~~~看了~~~不会~~~

楼上的方法看上去确实是可行的，谢谢了。这个问题我自己又从数学上推导了一下，和你讨论一下。
假设数组长度也就是元素总数为n，其中非0元素数量为m，额定最大非0元素数量为L，则消除多余非0元素的程序执行次数的数学期望为

如上例中，n=10,m=4,L=2，则执行次数的数学期望为5.8。我实验过，每1000次运行，平均执行次数在5.7-5.9之间跳动，说明公式正确。

楼上朋友的方法我也推导了一下，由非0元素组成的数组比原数组小许多，但某一非0元素被选后不可再选，因为随机选择的问题回到了上例的大数组中，但规模已经缩小，于是公式发生微小变化，为，上例数据中，它的数学期望为2.5。但是这个方法多了一步选择前的遍历原数组的操作，这部分时间将抵消5.8-2.5=3.3的时间。两种方法哪个好关键看3.3次执行和n长度数组的遍历时间哪个更长。

有意思，欢迎继续讨论。

非要做的话，用空间平衡时间是必要的。

上面的期望就不懂 了，不喜欢分析，

用空间平衡时间没问题呀，请给个方法了。现在对空间要求一般不高的

对了,数组可以改成一唯就可以了,相当于索引表,只记录在原数组中的位置,
而判断是否为0,则可到原表上查找和修改.这样空间也就少了.

通俗的说,因为非0数远远小于0元素,所以这办法可以提高效率.
而之前取随机数很有导致假死循环的可能(每次随机都取到0,毕竟这种概率很大).