{"image_url":null,"url":"https://mozk-2.hatenadiary.org/entry/20100206/1265460404","blog_title":"\u58ca\u308c\u305f\u8a08\u7b97\u6a5f","version":"1.0","height":"190","author_name":"Mozk","provider_name":"Hatena Blog","blog_url":"https://mozk-2.hatenadiary.org/","author_url":"https://blog.hatena.ne.jp/Mozk/","width":"100%","type":"rich","provider_url":"https://hatena.blog","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmozk-2.hatenadiary.org%2Fentry%2F20100206%2F1265460404\" title=\"\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u30a4\u30f3\u30c8\u30ed\u30c0\u30af\u30b7\u30e7\u30f3 Chapter 8 - \u58ca\u308c\u305f\u8a08\u7b97\u6a5f\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","categories":["CLRS"],"title":"\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u30a4\u30f3\u30c8\u30ed\u30c0\u30af\u30b7\u30e7\u30f3 Chapter 8","description":"\u7dda\u5f62\u6642\u9593\u30bd\u30fc\u30c6\u30a3\u30f3\u30b0\u3002\u6bd4\u8f03\u30bd\u30fc\u30c8\u304cnlogn\u304b\u304b\u308b\u3053\u3068\u306e\u8a3c\u660e\u3068\u3001\u305d\u306e\u7d50\u679c\u3092\u5229\u7528\u3057\u305f\u5225\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u8a08\u7b97\u91cf\u306e\u4e0b\u754c\u306e\u8a3c\u660e\u3002oblivious\u306asort\u3002 Exercise 8.1-1 n-1 Exercise 8.2-4 def exercise_8_2_4(a,k) n = a.length c = Array.new(k+1) for i in 0..k c[i] = 0; end for i in 0...n c[a[i]] += 1 end for i in 1..k c[i] += c[i-1] end return lambda{|a,b| if a == 0 c[b] else c\u2026","published":"2010-02-06 21:46:44"}