首页 > 代码库 > 线性时间选择
线性时间选择
线性时间选择
题目:给定n个元素和一个整数k,要求用O(n)时间找出这n个元素中第k小元素。
import java.util.Scanner; public class Main { static int kmin;// 第k小的数 static int knum;// 第k个数 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } knum = scanner.nextInt() - 1;// -1是为了让knum表示的是数组下标 getKmin(0, n - 1, nums); System.out.println(kmin); } scanner.close(); } // 得到第k小的元素 private static void getKmin(int i, int j, int[] nums) { int temp = quickSort(i, j, nums); if (temp < knum) { getKmin(temp + 1, j, nums); } else if (temp > knum) { getKmin(i, temp - 1, nums); } else { kmin = nums[temp]; } } // 数组快速排序(一趟) private static int quickSort(int i, int j, int[] nums) { int key = nums[i]; while (i != j) { while (i < j && nums[j] > key) { j--; } if (i < j) { nums[i] = nums[j]; } while (i < j && nums[i] < key) { i++; } if (i < j) { nums[j] = nums[i]; } } nums[i] = key; // i记录下标位置 return i; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。