package Alg1;import java.util.ArrayList;public class Knumbers { /*** * 问题说明： * 给定一组排列好的数字，长度为n，如果该列数字中某个数字比在它之前的数字都大，比它之后的都小， * 那么该数字就叫作K数，请用O(n)的时间复杂度找出所有的K数 * 解决思路： * 首先从前往后遍历， 选择当前遇到的最大的值覆盖数组内的值 例如 1 3 7 5 6 8 ， * 覆盖后应该为 1 3 7 7 7 8 然后在从后往前遍历，选择当前遇到的最小的覆盖当前的位置， * 上述数组就会变成 1 3 5 5 6 8 在这两次遍历完成之后 相当于会得到两个不同的数组， * 此时此时只需要比较两个新数组上对应位置的值 是否相等就好，如果相等则为K数，否则， * 就不是K数（其实上面只需要一个辅助数组就行，第二次进行 * 遍历用最小值替代时并不需要存储，直接和原数组进行比较得到结果就可以了） * * @param arr 输入数组 * * @return 得到所有的K数，一个动态数组 */ public ArrayList<Integer> findKnumbers(int arr[]) { ArrayList<Integer> returnArr = new ArrayList<Integer>(); // 定义一个辅助数组 int[] newint = new int[arr.length]; // 第一次循环，用最大值替换当前值 int MAX = 0; for (int i = 0; i < newint.length; i++) { if (arr[i] > MAX) { MAX = arr[i]; } newint[i] = MAX; // System.out.print(newint[i]+" "); } int MIN = 65535; // 得到当前最小值并且与之前替换好的数组进行比较 for (int i = arr.length - 1; i >= 0; i--) { if (arr[i] < MIN) { MIN = arr[i]; } // 若相等，那么就是K数 if (newint[i] == MIN) { returnArr.add(MIN); } } return returnArr; } public static void main(String[] args) { int arr[] = { 1, 9, 14, 3, 7, 5, 6, 8 }; System.out.println(new Knumbers().findKnumbers(arr)); }}
