#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? 需要改变原数组


登录后回复
 

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