数组去重(时间复杂度nlgn,时间复杂度o(1))

原创
2018/11/10 15:37
阅读数 2.8K
public static void quickSort(int[] numArr, int left, int right) {
    //如果left等于right,即数组只有一个元素,直接返回
    if (left >= right) {
        return;
    }
    //设置最左边的元素为基准值
    int key = numArr[left];
    //数组中比key小的放在左边,比key大的放在右边,key值下标为i
    int i = left;
    int j = right;
    while (i < j) {
        //j向左移,直到遇到比key小的值
        while (numArr[j] >= key && i < j) {
            j--;
        }
        //i向右移,直到遇到比key大的值
        while (numArr[i] <= key && i < j) {
            i++;
        }
        //i和j指向的元素交换
        if (i < j) {
            int temp = numArr[i];
            numArr[i] = numArr[j];
            numArr[j] = temp;
        }
    }
    numArr[left] = numArr[i];
    numArr[i] = key;
    // 递归调用
    quickSort(numArr, left, i - 1);
    quickSort(numArr, i + 1, right);
}
public static void main(String args[]) {
    // 初始化数组
    int[] numArry = {1, 1, 6, 2, 1, 6, 3, 3, 5, 7};
    int start = 0;
    int end = numArry.length - 1;
    quickSort(numArry, start, end);
    int tempNum = numArry[0];
    for (int i = 0; i < numArry.length; i++) {
        if (i == 0) {
            System.out.println(tempNum);
            continue;
        }
        if (tempNum != numArry[i]) {
            System.out.println(numArry[i]);
        }
        tempNum = numArry[i];
    }
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部