如何让15个变量随机代入1-15这15个不同的数字

新月の道化师

弱弱的问下21L...
^=是什么意思,找了下米找到...
交换位置的方法总觉得有些怪怪的...偶还是觉得直接用hash最方便...

================
想了下子,偶觉得交换似乎是牺牲了时间复杂度换取空间复杂度的感觉,感觉还是从数组或者hash中抽取效率要高些...个人感觉>_<

亿万星辰

从来没想过用这样的方法来实现呢……
看了看确实有那么点意思~学习了~

这个交换变量值的方法第一次见，不错。

还有这个“改变动态数组的长度效率无论如何也比不上交换元素”这个是怎么知道的？
我测了一下效率是我那个方法的两倍~

越前リョーマ

17# 越前リョーマ


如此说来，事件有何意义呢？
tommay 发表于 2009-7-13 08:34

意义在于事件也能完成这个事情。
你问的是如何完成，我这不完成了么？麻烦不等于无法完成。

玄月

总之都在借帖聊天了 - - 说来我那个不好么，何必弄这么多复杂的算法呢

紫苏

弱弱的问下21L...
^=是什么意思,找了下米找到...
交换位置的方法总觉得有些怪怪的...偶还是觉得直接用hash最方便...
新月の道化师 发表于 2009-7-13 15:09

自异或运算，这是最高效的交换两个整数的方法～
两次异或相同的数后会得到原数，所以可以用来交换两个变量的值

浮点的话，则是用 +- 交换的方法～

想了下子,偶觉得交换似乎是牺牲了时间复杂度换取空间复杂度的感觉,感觉还是从数组或者hash中抽取效率要高些...个人感觉>_<
新月の道化师 发表于 2009-7-13 15:09

怎么会呢，从数组中抽取不也占用了一个数组嘛～最后得到的数也是需要空间占用的
而且就算换也是换了时间复杂度……

用了星子的那段代码，比较两个方法执行的时间，运算量大的时候就可以看出差别了：

1. def genRandom1(n)
   
2.   arr = Array.new(n)
   
3.   for i in 0...arr.size
   
4.     arr[i] = i
   
5.   end
   
6.   i = n - 1
   
7.   begin
   
8.     r = rand(i)
   
9.     arr[i] ^= arr[r]
   
10.     arr[r] ^= arr[i]
    
11.     arr[i] ^= arr[r]
    
12.   end until (i -= 1) < 1
    
13.   return arr
    
14. end
    
15. 
    
16. def genRandom2(n)
    
17.   array = (0...n).to_a
    
18.   result = []  
    
19.   n.times{result.push(array.delete_at(rand(array.size)))}
    
20.   return result
    
21. end
    
22. 
    
23. a = Time.now
    
24. genRandom1(60000)
    
25. p Time.now - a
    
26. 
    
27. a = Time.now
    
28. genRandom2(60000)
    
29. p Time.now - a

复制代码

动态数组也是线性数据结构，底层还是静态的顺序数组，当数组需要插入/删除元素时，就会有一个线性的批量元素替换，比如插入时从插入点往后的元素依次后移，删除时则是依次往前移～

亿万星辰

研究到这么深的层次了，厉害……  = =|||

IamI

我是来飘的，无法想像LZ看到3页回帖时的表情
不知道用Table效率如何

tommay

我是一块砖，每每有这种技术贴，我都是用来抛的= =