@ScriptOJ 3路划分可以左右扫描啊。。。所以只要3路配合左右扫描就可以尽可能少交换元素了。。虽然逆序最终肯定是N^2这个变不了,但是就不用每次划分动移动整个区间了,毕竟修改比读取慢。。
[5, 4, 3, 2, 1] -> [4, 3, 2, 1, 5] -> [3, 2, 1, 4, 5] -> [2, 1, 3, 4, 5] -> [1, 2, 3, 4, 5] (交换15次)
[5, 4, 3, 2, 1] -> [1, 4, 3, 2, 5] -> [1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5] (交换3次)

CodeHz
@CodeHz
1010
得分
70
声望
63
帖子
1501
资料浏览
16
粉丝
4
关注
CodeHz 发布的帖子
-
RE: #82 数组中的数据划分(二)
-
RE: 检查一个函数是否被绑定
@ScriptOJ 这个name的方法并不准确。。比如下面这么写。。。
fn = ({['bound a']() {}})['bound a']
-
RE: #82 数组中的数据划分(二)
@ScriptOJ 但是市面上看到的写法都是左右扫描的写法。。。三路划分也可以左右扫描。。效率也不低(如果遇到逆序的情况就不会搬运整个数组了)
-
RE: #82 数组中的数据划分(二)
@ScriptOJ 大概说的是这种写法吧//这样确实只有一个循环,但是要交换好多次,,,很多交换都是不必要的
const swap = (a, i, j) => [a[i], a[j]] = [a[j], a[i]] const partition3way = (a, lo = 0, hi = a.length - 1) => { let lt = lo, gt = hi const v = a[lo] let i = lo while (i <= gt) { if (a[i] < v) swap(a, lt++, i++) else if (a[i] > v) swap(a, i, gt--) else i++ } }
-
RE: #82 数组中的数据划分(二)
@ScriptOJ 不是吧,一个大循环里面肯定得套两个小循环来找小于锚点的值和大于锚点的值啊。。。毕竟复杂度摆在那里,不可能优化成一个循环的啊
-
RE: #81 单例模式
proxy秒杀系列 2333
const singletonify = fn => { const one = new fn() return new Proxy(fn, { construct(target, argumentsList, newTarget) { return one } }) }
-
RE: #80 数组中的数据划分
const partition = arr => { const p = arr[0] let l = 1 let h = arr.length - 1 if (l >= h) return for(;;) { while (l < h && arr[l] <= p) l++ while (h > l && arr[h] >= p) h-- if (l >= h) break [arr[l], arr[h]] = [arr[h], arr[l]] } arr[arr.length - 1] = arr[l] arr[l] = p }
-
RE: #79 灵魂交换
const exchange = (a, b) => { const protos = [a, b].map(o => Object.getPrototypeOf(o)); //这里的分号是必要的 [b, a].forEach((o, i) => Object.setPrototypeOf(o, protos[i])) }
PS:
@ScriptOJ 话说为啥这里用不了<!--注释语法(虽然非标准,但是看着像一个箭头,比//逼格高)。。。node/chrome都是支持的,但是评测系统会提示Unexpected token
,但是放在eval里却又没事。。。。又是一个bug