一、快速排序
给你一个整数数组 nums，请你将该数组升序排列。
思路和算法
image.png
代码
class Solution {
int partition(vector<int>& nums, int l, int r) {
int pivot = nums[r];
int i = l - 1;
for (int j = l; j <= r - 1; ++j) {
if (nums[j] <= pivot) {
i = i + 1;
swap(nums[i], nums[j]);
}
}
swap(nums[i + 1], nums[r]);
return i + 1;
}
int randomized_partition(vector<int>& nums, int l, int r) {
int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
swap(nums[r], nums[i]);
return partition(nums, l, r);
}
void randomized_quicksort(vector<int>& nums, int l, int r) {
if (l < r) {
int pos = randomized_partition(nums, l, r);
randomized_quicksort(nums, l, pos - 1);
randomized_quicksort(nums, pos + 1, r);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
srand((unsigned)time(NULL));
randomized_quicksort(nums, 0, (int)nums.size() - 1);
return nums;
}
};
class Solution:
def randomized_partition(self, nums, l, r):
pivot = random.randint(l, r)
nums[pivot], nums[r] = nums[r], nums[pivot]
i = l - 1
for j in range(l, r):
if nums[j] < nums[r]:
i += 1
nums[j], nums[i] = nums[i], nums[j]
i += 1
nums[i], nums[r] = nums[r], nums[i]
return i
def randomized_quicksort(self, nums, l, r):
if r - l <= 0:
return
mid = self.randomized_partition(nums, l, r)
self.randomized_quicksort(nums, l, mid - 1)
self.randomized_quicksort(nums, mid + 1, r)
def sortArray(self, nums: List[int]) -> List[int]:
self.randomized_quicksort(nums, 0, len(nums) - 1)
return nums
二、二分
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
二分查找
image.png
class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1;
while(low <= high){
int mid = (high - low) / 2 + low;
int num = nums[mid];
if (num == target) {
return mid;
} else if (num > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
};
class Solution:
def search(self, nums: List[int], target: int) -> int:
low, high = 0, len(nums) - 1
while low <= high:
mid = (high - low) // 2 + low
num = nums[mid]
if num == target:
return mid
elif num > target:
high = mid - 1
else:
low = mid + 1
return -1
三、第k大数
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
方法一：基于快速排序的选择方法
image.png
class Solution {
public:
int quickSelect(vector<int>& a, int l, int r, int index) {
int q = randomPartition(a, l, r);
if (q == index) {
return a[q];
} else {
return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
}
}
inline int randomPartition(vector<int>& a, int l, int r) {
int i = rand() % (r - l + 1) + l;
swap(a[i], a[r]);
return partition(a, l, r);
}
inline int partition(vector<int>& a, int l, int r) {
int x = a[r], i = l - 1;
for (int j = l; j < r; ++j) {
if (a[j] <= x) {
swap(a[++i], a[j]);
}
}
swap(a[i + 1], a[r]);
return i + 1;
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
}
};
方法二：基于堆排序的选择方法
我们也可以使用堆排序来解决这个问题——建立一个大根堆，做 k - 1k−1 次删除操作后堆顶元素就是我们要找的答案。在很多语言中，都有优先队列或者堆的的容器可以直接使用，但是在面试中，面试官更倾向于让更面试者自己实现一个堆。所以建议读者掌握这里大根堆的实现方法，在这道题中尤其要搞懂「建堆」、「调整」和「删除」的过程。
class Solution {
public:
void maxHeapify(vector<int>& a, int i, int heapSize) {
int l = i * 2 + 1, r = i * 2 + 2, largest = i;
if (l < heapSize && a[l] > a[largest]) {
largest = l;
}
if (r < heapSize && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
swap(a[i], a[largest]);
maxHeapify(a, largest, heapSize);
}
}
void buildMaxHeap(vector<int>& a, int heapSize) {
for (int i = heapSize / 2; i >= 0; --i) {
maxHeapify(a, i, heapSize);
}
}
int findKthLargest(vector<int>& nums, int k) {
int heapSize = nums.size();
buildMaxHeap(nums, heapSize);
for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
swap(nums[0], nums[i]);
--heapSize;
maxHeapify(nums, 0, heapSize);
}
return nums[0];
}
};
