0

我创建了一个SortableArray类的实例

let test = new SortableArray([0, 50, 20, 10, 60, 30]);

然后我像这样调用quickselect实例来找到第一个最低值，第一个最低值实际上是第二低的值，因为它是零索引的。

test.quickselect(1, 0, test.array.length - 1);

然后我得到 undefined，这没有任何意义，因为 quickselect 方法包含一个 return 语句。

class SortableArray{
  constructor(array){
    this.array = array;
  }



swap(pointer1, pointer2){
    let temporary = this.array[pointer1];
    this.array[pointer1] = this.array[pointer2];
    this.array[pointer2] = temporary 
}



partition(leftPointer, rightPointer) {
    let count = 0;
    let temporary;
    let pivotPosition = rightPointer;
    let pivot = this.array[pivotPosition];
    rightPointer -= 1; 
    do{

      while((this.array[leftPointer] < pivot)  && (leftPointer <= rightPointer)){
        leftPointer++;
      }  

      while((this.array[rightPointer] > pivot) && (leftPointer <= rightPointer)){
        rightPointer--;
      }
      if((leftPointer <= rightPointer)){
        this.swap(leftPointer,rightPointer);
        continue;
      }
      break;
    }while((leftPointer !== rightPointer) && (leftPointer <= rightPointer));

    this.swap(leftPointer, pivotPosition);
    return leftPointer;
}



quickselect(kthLowestValue, leftIndex, rightIndex){
    debugger;
    if(rightIndex - leftIndex <= 0){
      return this.array[leftIndex];
    }

    let pivotPosition = this.partition(leftIndex, rightIndex);

    if(kthLowestValue < pivotPosition){
      this.quickselect(kthLowestValue, leftIndex, pivotPosition - 1);
    }else if(kthLowestValue > pivotPosition){
      this.quickselect(kthLowestValue, pivotPosition + 1, rightIndex);
    }else{
      **return this.array[pivotPosition];**
    }
  }
}
4

1 回答 1

0

quickselect您需要在调用代码时返回值if/else，而不仅仅是else像这样

if (kthLowestValue < pivotPosition) {
            return this.quickselect(kthLowestValue, leftIndex, pivotPosition - 1);
        } else if (kthLowestValue > pivotPosition) {
            return this.quickselect(kthLowestValue, pivotPosition + 1, rightIndex);
        } else {
            return this.array[pivotPosition];
        }

这是一个小的 mocha 测试文件来确认这一点：

import SortableArray from "./SortableArray";

describe('Check code', function () {
    it('Run a test', function () {
        let test = new SortableArray([0, 50, 20, 10, 60, 30]);
        let x = test.quickselect(1, 0, test.array.length - 1);
        console.log(x);
    })

})

新代码的结果是：10

于 2019-12-22T14:43:07.680 回答