题解 | #在二叉树中找到两个节点的最近公共祖先#

import java.util.*; public class Solution{ public ArrayList GetLeastNumbers_Solution(int[] input,int k){ ArrayList result = new ArrayList<>(); if(k > input.length || k == 0) return result; quickSort(input,result,k,0,input.length - 1); return result;

}
public void quickSort(int[] input,ArrayList<Integer> result,int k,int left,int right){
    int start = left;
    int end = right;
    while(left < right){
        while(left < right && input[right] >= input[start]){
            right -- ;
        }
        while(left < right && input[left] <= input[start]){
            left ++;
        }
        swap(input,left,right);
    }
    swap(input,start,left);
    if(left > k){
        quickSort(input,result,k,start,left -1);
       
    }else if(left < k){
         quickSort(input,result,k,left+1,end);
    }else{
        for(int m = 0;m < k;m++){
            result.add(input[m]);
        }
    }
}
public void swap(int[] input,int left,int right){
    if(left == right) return;
    int temp = input[left];
    input[left] = input[right];
    input[right] = temp;
}

}

// while (left < right && input[right] >= input[start]) { // right--; // } // while (left < right && input[left] <= input[start]) { // left++; // } // swap(input, left, right); // } // swap(input, left, start); // //注意这里，start是数组中元素的下标。在start之前的元素都是比start指向的元素小， // //后面的都是比他大。如果k==start，正好start之前的k个元素是我们要找的，也就是 // //数组中最小的k个，如果k>start，说明前k个元素不够，我们还要往后再找找。如果 // //k<start，说明前k个足够了，我们只需要在start之前找k个即可。 // if (left > k) { // quickSort(input, res, k, start, left - 1); // } else if (left < k) { // quickSort(input, res, k, left + 1, end); // } else { // //取前面的k个即可 // for (int m = 0; m < k; ++m) { // res.add(input[m]); // } // } // }

// private void swap(int[] arr, int i, int j) { // if (i == j) // return; // int temp = arr[i]; // arr[i] = arr[j]; // arr[j] = temp; // } // }