215. 数组中的第K个最大元素

步骤

通过堆排序来获取第k大的元素。
1. 从第一个非叶子节点开始向上初始化堆，对于当前堆顶元素向下调整堆。
2. 删除k-1个元素后，堆顶元素是第k个最大。

Go代码

package sort

func findKthLargest(nums []int, k int) int {
	initHeap(nums)
	for i := 0; i < k - 1; i++ {
		nums[0], nums[len(nums) - 1] = nums[len(nums) - 1], nums[0]
		nums = nums[0:len(nums) - 1]
		adjustDown(nums, 0)
	}
	return nums[0]
}

func initHeap(nums []int) {
	for i := len(nums) / 2; i >= 0; i-- {
		adjustDown(nums, i)
	}
}

func adjustDown(nums []int, index int) {
	for {
		j := index * 2 + 1
		if j >= len(nums) || j < 0 {
			break
		}

		maxIndex := j
		if j + 1 < len(nums) && nums[j + 1] > nums[j] {
			maxIndex = j + 1
		}

		if nums[maxIndex] <= nums[index] {
			break
		}

		nums[index], nums[maxIndex] = nums[maxIndex], nums[index]
		index = maxIndex
	}
}

Java代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        initHeap(nums);
        for (int i = 0; i < k - 1; i++) {
            int temp = nums[0];
            nums[0] = nums[nums.length - i - 1];
            nums[nums.length - i - 1] = temp;

            adjustDown(nums, 0, nums.length - i - 1);
        }
        return nums[0];
    }

    private void initHeap(int[] nums) {
        for (int i = nums.length / 2; i >= 0; i--) {
            adjustDown(nums, i, nums.length);
        }
    }

    private void adjustDown(int[] nums, int index, int n) {
        for (; ;) {
            int j = index * 2 + 1;
            if (j >= n || j < 0) {
                break;
            }

            if (j + 1 < n && nums[j + 1] > nums[j]) {
                j++;
            }

            if (nums[j] <= nums[index]) {
                break;
            }

            int temp = nums[j];
            nums[j] = nums[index];
            nums[index] = temp;

            index = j;
        }
    }
}

912. 排序数组

步骤

通过递归来实现指定范围的快速排序。
1. 首元素是基准，从右向左寻找第一个比基准小的数放到左边，从左向右寻找第一个比基准大的数放到右边，最终的p位置存放基准。
2. 递归排序基准左边的子序列，递归排序基准右边的子序列，直到子序列长度是1。

GO代码

package sort

func sortArray(nums []int) []int {
	quickSort(nums, 0, len(nums) - 1)
	return nums
}

func quickSort(nums []int, left, right int) {
	if left >= right {
		return
	}

	pivot := nums[left]
	p := left
	i := left
	j := right
	for i <= j {
		for j >= p && nums[j] >= pivot {
			j--
		}
		if j >= p {
			nums[p] = nums[j]
			p = j
		}

		for i <= p && nums[i] <= pivot {
			i++
		}
		if i <= p {
			nums[p] = nums[i]
			p = i
		}
	}

	nums[p] = pivot
	quickSort(nums, left, p - 1)
	quickSort(nums, p + 1, right)
}

Java代码

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = nums[left];
        int p = left;
        int i = left;
        int j = right;
        while (i <= j) {
            while (j >= p && nums[j] >= pivot) {
                j--;
            }
            if (j >= p) {
                nums[p] = nums[j];
                p = j;
            }

            while (i <= p && nums[i] <= pivot) {
                i++;
            }
            if (i <= p) {
                nums[p] = nums[i];
                p = i;
            }
        }
        nums[p] = pivot;

        quickSort(nums, left, p - 1);
        quickSort(nums, p + 1, right);
    }
}

75. 颜色分类

步骤

快速排序的三向切分排序变种
low表示小于基准的右边界，high表示大于基准的左边界。
小于基准的数字放左边，大于基准的数字放右边。

GO代码

func sortColors(nums []int)  {
    pivot := 1
    i := 0
    low := 0
    high := len(nums) - 1
    for i <= high {
        if nums[i] <= pivot {
            if nums[i] < pivot {
                nums[i], nums[low] = nums[low], nums[i]
                low++
            }
            i++
        } else {
            nums[i], nums[high] = nums[high], nums[i]
            high--
        }
    }
}

Java代码

class Solution {
    public void sortColors(int[] nums) {
        int pivot = 1;
        int i = 0;
        int low = 0;
        int high = nums.length - 1;

        while (i <= high) {
            if (nums[i] < pivot) {
                if (i > low) {
                    int temp = nums[low];
                    nums[low] = nums[i];
                    nums[i] = temp;
                }

                low++;
                i++;
            } else if (nums[i] == pivot) {
                i++;
            } else {
                if (i < high) {
                    int temp = nums[high];
                    nums[high] = nums[i];
                    nums[i] = temp;
                }

                high--;
            }
        }
    }
}