给定一个长度为n的无序数组A和一个小于等于n的整数K，设计一个O(n)时间复杂度的算法，返回数组A中第K大的元素。请 写出算法的伪代码(c语言)和算法思想。

### 回答1：
可以使用快速选择算法来解决这个问题。

快速选择算法的基本思想是利用快排的思想，不过只需要排序数组中的一个分界点，而不是整个数组。

伪代码：

int partition(int A[], int l, int r) {
    int pivot = A[r];
    int i = l - 1;
    for (int j = l; j <= r - 1; j++) {
        if (A[j] >= pivot) {
            i++;
            swap(A[i], A[j]);
        }
    }
    swap(A[i + 1], A[r]);
    return i + 1;
}

int quickSelect(int A[], int l, int r, int k) {
    if (k > 0 && k <= r - l + 1) {
        int index = partition(A, l, r);
        if (index - l == k - 1) {
            return A[index];
        } else if (index - l > k - 1) {
            return quickSelect(A, l, index - 1, k);
        } else {
            return quickSelect(A, index + 1, r, k - index + l - 1);
        }
    }
    return INT_MAX;
}

// 返回数组A中第K大的元素
int findKthLargest(int A[], int n, int k) {
    return quickSelect(A, 0, n - 1, n - k + 1);
}

时间复杂度：期望为O(n)，最坏情况下为O(n^2)。

### 回答2：
算法思想：
1. 使用快速选择算法，通过快速划分（partition）找出数组A中的一个主元（pivot）。
2. 将主元左侧的元素都大于或等于主元，将主元右侧的元素都小于或等于主元。
3. 比较主元在数组中的位置与K的大小，如果主元的位置等于K，则返回主元；如果主元的位置大于K，则递归在主元左侧的子数组中查找第K大的元素；如果主元的位置小于K，则递归在主元右侧的子数组中查找第K大的元素。

伪代码：
1. 定义函数quickSelect(A, left, right, K)：
2. 如果left等于right，返回A[left]。
3. 选择主元pivot为A[right]。
4. 将数组A进行划分，得到主元的位置p，使得左侧的元素都大于或等于主元，右侧的元素都小于或等于主元。
5. 如果p等于K，返回A[p]。
6. 如果p大于K，递归调用quickSelect(A, left, p - 1, K)。
7. 如果p小于K，递归调用quickSelect(A, p + 1, right, K)。
8. 定义函数findKthLargest(A, K)：
9. 返回quickSelect(A, 0, n - 1, n - K)。

这个算法的时间复杂度为O(n)，因为每次都可以快速划分出一个主元。