#82 数组中的数据划分(二)


  • 0
    administrators

    完成一个函数 partition3way,它接受一个数组作为参数。它会搬动数组中的元素,使得所有小于第一个项的元素都搬动到它的左边,所有大于第一个项的元素都搬动到右边,等于它的都放在中间。例如:

    const arr = [3, 1, 3, 6, 2, 3, 4, 5]
    partition3way(arr)
    console.log(arr) // => [2, 1, 3, 3, 3, 6, 4, 5] or [1, 2, 3, 3, 3, 4, 5, 6]
    

    输入的数组的第一个项是 3,所以最后小于 3 的 1、2 的都到了左边,大于 3 的 4, 5, 6 都到了右边,3 都放在了中间。

    请你在不能使用任何数组原生方法,只能使用循环和赋值的情况下完成 partition3way 函数。


  • 0
    administrators

    hint:#80 其实考察的是快排,这题是三路快排。


  • 0
    administrators

    因为有暴力破解漏洞(例如插排),调整题目要求,只能使用一次循环。


  • 0

    @ScriptOJ 原地快排也不止需要一个循环。。。


  • 0
    administrators

    @CodeHz 3 way 就是一个 loop


  • 0
    administrators

    还是得用 TLE 来限制暴力解,用循环限制有点掩耳盗铃


  • 0

    @ScriptOJ 不是吧,一个大循环里面肯定得套两个小循环来找小于锚点的值和大于锚点的值啊。。。毕竟复杂度摆在那里,不可能优化成一个循环的啊


  • 0
    administrators

    @CodeHz 2 way 你那两个循环加起来也是扫一边数组。复杂度是因为递归吧


  • 0

    @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++
      }
    }

  • 0
    administrators

    @CodeHz 嗯,解决的问题不一样。如果数组里面是很多重复的 key,那就不用交换很多了。而左右扫的方案可能会退化成 O(n^2)。


  • 0

    @ScriptOJ 但是市面上看到的写法都是左右扫描的写法。。。三路划分也可以左右扫描。。效率也不低(如果遇到逆序的情况就不会搬运整个数组了)


  • 0
    administrators

    @CodeHz 2 way 正逆序都会扫到两端吧。这时候就不能 half divide,从两端 divide 就会 N^2。而如果大量重复的 key 不用 3 way 的话,是肯定落到 N^2。


  • 0

    @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次)


  • 0
    administrators

    @CodeHz 3 way 当然可以配合左右扫,我上面的左右扫方案特指 2 way,并不是说 3 way 就不能左右扫,😄


  • 0

    没有排序,而且循环点到即止,应该可以吧

    const partition3way = (arr) => {
      var p = 0
      var v = arr[0]
      var len = arr.length
      for(let i = 1; i < len; i++) {
        if(v > arr[i]) {
          //与小的数换位
          arr[p] = arr[i]
          arr[i] = v
          //p+1可能是一个与参考值相等的数
          p++
        }else if(v < arr[i]){
          //后面大的数与后面小的数换位
          for(var j = i + 1; j < len; j++) {
            if(arr[j] <= v) {
              [arr[i], arr[j]] = [arr[j], arr[i]]
              //如果进行了交互,i不后移
              i--
              break
            }
          }
          //后面已经没有更小的数,计算结束
          if(j === len) return
        }
      }
    }
    

    一个你用了还想用的前端表单验证工具 https://github.com/WLDragon/SMValidator


  • 0

    const partition3way = (arr) => {
      let t
      let j = 0
      let first = arr[0]
      for (let i = 1; i < arr.length; i++) {
          if (arr[i] <= first) {
              t = arr[i]
              let l = i
              for (; l > j; l--) {
                  arr[l] = arr[l - 1]
              }
              arr[l] = t
              if (t !==first) {
                  j++
              }
          }
      }
    }
    

    我的思路是这样的:
    把小于或等于第一个数的数都放在第一个数前面,当然也可以判断如果是等于的话放在第一个前面,这样效率会更高,但是这里懒得写了
    如数组:[3, 1, 3, 6, 2, 3, 4, 5]

    • 1小于3,1放3前,即互换
    • 3相同,放3前,即互换(懒得再判断,就按小于处理了)
    • 6比3大,不处理
    • 2比3小,与6交换,与3交换,与3交换,前面用j记录小于3的次数,所以2不用再与它们比较了,直接互换,反正前j位的数是小于3的

  • 0

    const partition3way = (arr) => {
    function swap(arr,a,b){
    if(arr[a] == arr[b]) return;
    arr[a] ^= arr[b];
    arr[b] ^= arr[a];
    arr[a] ^= arr[b];
    }
    let l = 0, i = 1, r = arr.length-1;
    let p = arr[0];

    while(i<=r){
    if(arr[i]<p)
    swap(arr,i++,l++);
    else if(arr[i]>p)
    swap(arr,i,r--)
    else
    i++;
    }
    }


登录后回复
 

与 ScriptOJ 的连接断开,我们正在尝试重连,请耐心等待