下面函数实现了从一个长度为n 的正整数数组中得到第K 小的数（无解返回-1），请分析它的平均时间复杂度为（） int partition(int arr[], int left, int right) { int j = left, tmp; for (int i = left; i < right; ++i){ if (arr[i] <= arr[right]){ tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; j += 1; } } tmp = arr[j]; arr[j] = arr[right]; arr[right] = tmp; return j; } int find_kth(int arr[], int n, int K) { int left = 0, right = n – 1; K -= 1; while (true){ int pivot = partition(arr, left, right); if (pivot == K) return arr[pivot]; if (pivot > K) right = pivot – 1; else left = pivot + 1; } return -1; }

区块链毕设网qklbishe.com为您提供问题的解答

下面函数实现了从一个长度为n的正整数数组中得到第K小的数（无解返回-1），请分析它的平均时间复杂度为（）

int partition(int arr[], int left, int right) {     int j = left, tmp;     for (int i = left; i < right; ++i){         if (arr[i] <= arr[right]){             tmp = arr[i];             arr[i] = arr[j];             arr[j] = tmp;              j += 1;         }     }     tmp = arr[j];     arr[j] = arr[right];     arr[right] = tmp;     return j; }  int find_kth(int arr[], int n, int K) {     int left = 0, right = n - 1;     K -= 1;     while (true){         int pivot = partition(arr, left, right);         if (pivot == K)             return arr[pivot];         if (pivot > K)             right = pivot - 1;         else             left = pivot + 1;     }     return -1; }

该算法是利用快排的思想，但是只对划分出的两组中的一个（第K小的数所在的组）进行递归，所以时间复杂度为O(N)。

23:20

以上就是关于问题下面函数实现了从一个长度为n 的正整数数组中得到第K 小的数（无解返回-1），请分析它的平均时间复杂度为（）
int partition(int arr[], int left, int right) { int j = left, tmp; for (int i = left; i < right; ++i){ if (arr[i] <= arr[right]){ tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; j += 1; } } tmp = arr[j]; arr[j] = arr[right]; arr[right] = tmp; return j; } int find_kth(int arr[], int n, int K) { int left = 0, right = n – 1; K -= 1; while (true){ int pivot = partition(arr, left, right); if (pivot == K) return arr[pivot]; if (pivot > K) right = pivot – 1; else left = pivot + 1; } return -1; }的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。

区块链NFT链游项目方科学家脚本开发培训