#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);
    }
    ···


登录后回复
 

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