# 数组去重（时间复杂度nlgn，时间复杂度o(1)）

2018/11/10 15:37

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