文章/答案/技术大牛

发布

社区首页 >问答首页 >给定一个枢轴x和一个列表1，将列表划分为三个部分

问给定一个枢轴x和一个列表1，将列表划分为三个部分
EN

Code Review用户

提问于 2019-03-20 15:22:41

回答 2查看 1.2K关注 0票数 3

任务：

给定一个枢轴x和一个列表1，将列表划分为三个部分。第一部分包含lst中小于x的所有元素，第二部分包含等于x的lst中的所有元素，第三部分包含lst中大于x排序的所有元素可以是任意的。例如，给定x= 10和lst = 9、12、3、5、14、10、10，一个分区可能是`9、3、5、10、10、12、14‘。

我的解决方案：

const createPartitionOf = (lst, pivot) => {
  const lessLst = lst.filter(x => x < pivot);
  const equalLst = lst.filter(x => x === pivot);
  const largerLst = lst.filter(x => x > pivot);
  return [...lessLst, ...equalLst, ...largerLst];
};

console.log(createPartitionOf([9, 12, 3, 5, 14, 10, 10], 10));

我的solution2：

const createPartitionOf2 = (lst, pivot) => {
  const lessLst = [];
  const equalLst = [];
  const largerLst = [];
  for (let i = 0; i < lst.length; i++) {
    if (lst[i] < pivot) {
      lessLst.push(lst[i]);
    } else if (lst[i] > pivot) {
      largerLst.push(lst[i]);
    } else {
      equalLst.push(lst[i]);
    }
  }
  return [...lessLst, ...equalLst, ...largerLst];
};

console.log(createPartitionOf2([9, 12, 3, 5, 14, 10, 10], 10));

javascript

algorithm

programming-challenge

functional-programming

回答 2

Code Review用户

发布于 2019-03-21 02:05:48

在第一个解决方案中，您将遍历列表3次，而在第二个解决方案中只遍历一次。考虑到函数标记，我想说的是，您需要的是reduce函数：

const flatten = (acc, x) => acc.concat(x)

const pivotPartition = (pivot, ary) => {
  const toOrdered = (triplet, n) => {
    let [less, equal, greater] = triplet

    switch(true) {
      case n < pivot: less.push(n); break
      case n > pivot: greater.push(n); break
      default: equal.push(n)
    }

    return triplet
  }

  return ary.reduce(toOrdered, [[], [], []]).reduce(flatten)
}

如果您也想对子数组进行排序，那么整个过程只是一个ary.sort((a, b) => a - b)，尽管它正在改变列表，但它不是一个功能解决方案。

票数 5

Code Review用户

发布于 2021-05-08 19:54:32

考虑两个指针，低和高是持续向中心方向移动，最终x ==值将居中。

        int x = 10;
        Integer[] intList = new Integer[] {9, 12, 3, 5, 14, 17, 10, 10};
        int pointlow=0, pointhigh = intList.length-1;
        Integer arr[] = new Integer[intList.length];
        
        for(int i=0; i<= intList.length-1; i++) {
            if(intList[i] < x) {
                arr[pointlow] = intList[i];
                pointlow++;
            }
            else {
                arr[pointhigh] = intList[i];
                pointhigh--;
            }
        }       
        System.out.println(Arrays.asList(arr));

票数 -1

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/215848

复制

相似问题

问给定一个枢轴x和一个列表1，将列表划分为三个部分
EN

回答 2

Code Review用户

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问给定一个枢轴x和一个列表1，将列表划分为三个部分EN

回答 2

Code Review用户

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问给定一个枢轴x和一个列表1，将列表划分为三个部分
EN