#80 数组中的数据划分


  • 0
    administrators

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

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

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

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


  • 2

    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
    }
    

  • 0

    快速排序

    const partition = (arr) => {
      const swap = (a, i, j) => [a[i], a[j]] = [a[j], a[i]]
      
      const v = arr[0]
      let i = 0
      let k = 1
      let j = arr.length - 1
      
      while(k <= j) {
        if(arr[k] < v) swap(arr, i++, k++)
        else if(arr[k] > v) swap(arr, j--, k)
        else k++
      }
    }
    

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


  • 0

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

  • 0

    const partition = (arr) =>{
    var first=arr[0];
    var array=[first];
    for(var i=1;i<arr.length;i++){
    if(first>arr[i]){
    array.unshift(arr[i]);
    }else{
    array.push(arr[i]);
    }
    }
    return array;
    }
    本地测试是对的啊,难道是改原数组吗


  • 0

    const partition = (arr) => {
            let val = arr[0], end = arr.length - 1, start = 0
    	for (let i = 1; i <= end; i++) {
    		if (arr[i] < val) {
    			[arr[start++], arr[i]] = [arr[i], arr[start]]
    		} else if (arr[i] > val) {
    			[arr[i--], arr[end--]] = [arr[end], arr[i]]
    		}
    	}
    }
    

  • 0

    const partition = (arr) => {
      const newArr = [];
      let i = 0;
      for (let val of arr) {
        if (val < arr[0]) newArr[i++] = val;
      }
      newArr[i++] = arr[0];
      for (let val of arr) {
        if (val >= arr[0]) newArr[i++] = val;
      }
      return newArr;
    }
    

    时间复杂度 O(n)... 2n == n 嘿嘿
    本地测试是好的,不知道是啥问题呢?望解答


  • 0

    @zachrey#80 数组中的数据划分 中说:

    const partition = (arr) => {
      const newArr = [];
      let i = 0;
      for (let val of arr) {
        if (val < arr[0]) newArr[i++] = val;
      }
      newArr[i++] = arr[0];
      for (let val of arr) {
        if (val >= arr[0]) newArr[i++] = val;
      }
      return newArr;
    }
    

    时间复杂度 O(n)... 2n == n 嘿嘿
    本地测试是好的,不知道是啥问题呢?望解答

    哦,不支持 for of? 需要改变原数组


  • 0

    const partition = (arr) => {
      function swap(arr, a, b) {
      [arr[a], arr[b]] = [arr[b], arr[a]]
    }
    
      let p = arr[0]
      let index = 0
      let len = arr.length
      for (let i = 1; i < len;) {
        if (arr[i] < p) {
          swap(arr, i, index)
          p = arr[i]
          index = i
          i++
        } else if (arr[i] > p) {
          swap(arr, i, len - 1)
          len--
        } else {
          i++
        }
      }
      return arr
    }
    
    

  • 0

    const partition = (arr) => {
      let k = arr[0];
      for(let i=0;i<arr.length;i++){
        if(k>arr[i]){
          let temp = arr[i];
          for(let j=i;j>=0;j--){
            arr[i] = arr[i-j];
          }
          arr[0] = temp;
        }
      }
      return arr;
    }
    

  • 0

    不能使用数组原生方法


  • 0

    const partition = (arr) => /* TODO */
    {
    let lf = arr[0]
    let count = 0
    for(let i = 1 ; i < arr.length ; i ++){
    let num = arr[i]
    if(num<lf){
    count++;
    arr[0]=num;
    for(let k = i ; k > count ; k --){
    arr[k]=arr[k-1];
    }
    arr[count]=lf;
    }
    }
    return arr;
    }


  • 0

    这个数据测试有问题吧,这样写明显是ok的啊。
    ···
    const partition = (arr) => /* TODO */
    {
    if(!arr || !(arr instanceof Array)) return [];
    let middleNum = arr[0],
    smallArr = [],//存放小数
    equArr= [],//相等的数
    bigArr = []; //存放大数
    for(var i=0;i<arr.length;i++)
    {
    if(arr[i]<middleNum) smallArr.push(arr[i]);
    else if(arr[i]>middleNum) bigArr.push(arr[i]);
    else equArr.push(arr[i]);
    }
    return smallArr.concat(equArr).concat(bigArr);
    }
    ···


  • 0

    规定不能使用任何数组方法,所以要计算边界值和边界序号(其前面有几个比他小的值),通过arr[--limit] = val 的赋值形式来处理。整个过程繁琐了很多。
    const partition = (arr) => {
    let arrCopy = Object.assign([],arr) ; //复制一个数组
    let limit = arrCopy[0] ; //边界值是第一个值
    let smallCount=0,limitIndex ;
    for(let i=0;i<arrCopy.length;i++){
    if(arrCopy[i]<limit){
    smallCount ++ ;
    }
    }
    limitIndex = smallCount ; // 比他小的数量即是边界值所在index位置
    arr[limitIndex] = limit ; // 在合适的位置放置界限值,其前面有smallCount个比他小的值
    for(let i=0;i<arrCopy.length;i++){
    if(arrCopy[i]<limit){
    arr[--smallCount] = arrCopy[i] ;
    }else{
    arr[++limitIndex] = arrCopy[i] ;
    }
    }
    return arr ;
    }


  • 0

    写的有点多,还是写出来了

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

  • 0

    const partition = (arr) => {
        const fisrt = arr[0];
        for(let i = 1,pos = 0,arrLen=arr.length;i<arrLen;i++){
            if(arr[i] <= fisrt){
                arr[pos++] = arr[i];
                arr[i] = arr[pos];
                arr[pos] = fisrt;
            }
        }
    }
    

登录后回复
 

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