#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

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


  • 1

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


  • 0

    arr[0]放在原位不动, 先将其他数分成[小于][等于][大于]三段, 然后将arr[0][小于]中最后一个数交换位置即可.

    例如: [3, 1, 3, 6, 2, 3, 4, 5] => [3, 1, 2, 3, 3, 4, 5, 6] => [2, 1,3, 3, 3, 4 ,5 ,6]

    然后问题转变成要将其他数分成[小于][等于][大于]三段. 我这里从左到右依次将数字加入, 同时维护加入的数字符合分段的要求. (与《算法导论》里面快排用的方法类似, 就是多分了一段).

    使用i, j, k将原始数组分成三段, arr[1 ~ k-1] 表示[小于], arr[k ~ j-1]表示[等于], arr[j ~ i -1]表示[大于].
    初始时i = j = k = 1表示整个序列没有数字, 这时满足[小于][等于][大于]性质(因为三段的长度都为0).

    i++表示加入arr[i]的数字到[大于]的尾端:

    (1)如果arr[i]的值大于arr[0], 则这个序列保持[小于][等于][大于]性质;

    例如: [3, 1, 3, 4] => [3, 1, 3, 4, 5] => [3, 1, 3, 4, 5]

    (2)如果arr[i]的值等于arr[0], 则需要将[大于]的第一个数(arr[j])与其交换, 并通过j++[大于]段的起始位置后移, 使得加入的数落入[等于]的尾部, 序列保持[小于][等于][大于]性质;

    例如: [3, 1, 3, 4] => [3, 1, 3, 4, 3] => [3, 1, 3, 3, 4]

    (3)如果arr[i]的值小于arr[0], 则在(2)的基础上再将加入的数与[等于]的第一个数(arr[k])交换, 并用k++使得加入的数落入[小于]的尾部, 序列保持[小于][等于][大于]性质;

    例如: [3, 1, 3, 4] => [3, 1, 3, 4, 2] => [3, 1, 3, 2, 4] => [3, 1, 2, 3, 4]

    n个数字依次加入, 加入后维护[小于][等于][大于]性质产生的交换不超过两次, 复杂度O(n)

    const partition3way = (arr) => {
      let len = arr.length;
      if(len <= 1) {
        return;
      }
      let pivot = arr[0];
      let i = 1, j = 1, k = 1;
      for(; i < len; ++i) {
        if(arr[i] > pivot) {
          continue;
        }
        if(i !== j) {
          let tmp = arr[i];
          arr[i] = arr[j];
          arr[j] = tmp;
        }
        if(arr[j] == pivot) {
          ++j;
          continue;
        }
        if(j !== k) {
          let tmp = arr[j];
          arr[j] = arr[k];
          arr[k] = tmp;
        }
        ++j;
        ++k;
      }
      if(k != 1) {
        let tmp = arr[k - 1];
        arr[k - 1] = pivot;
        arr[0] = tmp;
      }
    }
    

  • 0

    开始自己写了一个,用的最原始的交换数据的方法,后来看参考区的改进了一下,但是加了打印的时候会超时,注释掉的为之前的写法,之前的写法加了注释掉的打印也不会超时……

    const partition3way = (arr) => {
      const filv = arr[0];
      let j = 0;
      let k = arr.length -1;
      for(let i = 1; i< arr.length; i++) {
        if(arr[i] < filv) {
        	// const temp = arr[j];
        	// arr[j] = arr[i];
        	// arr[i] = temp;
        	[arr[i],arr[j]] = [arr[j],arr[i]];
        	j++;
        } else if (arr[i]>filv) {
        	if(i>k)  break;
        	// const temp = arr[k];
        	// arr[k] = arr[i];
        	// arr[i] = temp;
        	[arr[i],arr[k]] = [arr[k],arr[i]];
        	k--;
        	i--;
        }
        //console.log(arr);
      }
    }
    

  • 0

    用 (#80 数组中的数据划分)这道题的代码就可以直接通过了

    const partition = (arr) => {
       var newStr1 = "", newStr2 = "", newStr3 = "", str = "";
       for (let i = 0; i < arr.length; i++) {
           if (arr[0] > arr[i]) {
               newStr1 = arr[i] + "," + newStr1;
           }
           if (arr[0] === arr[i]) {
               newStr2 = newStr2 + arr[0] + ",";
           }
           if (arr[0] < arr[i]) {
               newStr3 = newStr3 + arr[i] + ",";
           }
       }
    
       str = newStr1 + newStr2 + newStr3;
    
       str = str.substring(0, str.length - 1);
    
       str.split(",").map((x, y)=>arr[y] = parseInt(x));
    
       return arr;
    };

登录后回复
 

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