六安品牌网站建设电话,世界500强企业关于优秀员工的12条核心标准,小程序开发外包,天津网站优化排名推广【1】题目#xff1a; 给定一个无序数组#xff0c;找到最长的单调自增子序列#xff08;不一定连续#xff0c;但是顺序不能乱#xff09;的长度#xff1b;
【2】看个荔枝#xff1a;给定数组 [10, 9, 2, 5, 3, 7, 101, 18] 输出结果为 [2, 3, 7, 101]。。算法时间…【1】题目 给定一个无序数组找到最长的单调自增子序列不一定连续但是顺序不能乱的长度
【2】看个荔枝给定数组 [10, 9, 2, 5, 3, 7, 101, 18] 输出结果为 [2, 3, 7, 101]。。算法时间复杂度一般为 O(n^2) 也可以优化到 O(nlgn)
【3】算法思路对无序数组做一次遍历 并找出最小最大值v1, v2及其下标i1, i2下一次循环遍历的范围是在 [i11, i2-1] 这个范围内找出 最小最大值 及其下标每次循环 counter 2...... 算法结束标志是 i1 小于i2且当 i1等于i2时 表明 单调自增子序列的长度是奇数所以counter算法实现如下下面算法的时间复杂度是 O(n^2) // input: [10, 9, 2, 5, 3, 7, 101, 18]
// output: [2, 3, 7, 101]public class NiBiNuCycle {static int counter 0;public static void main(String[] args) {
// int[] array {10, 9, 2, 5, 3, 7, 101, 18};int[] array {10, 90, 76, 12, 25, 36, 78, 99, 177, 132, 156};find(array, 0, array.length-1);System.out.println(result counter);}static void find(int[] array, int i1, int i2) {int ci10, ci20; // ci1, ci2 是 i1 和 i2 的 copy// v1 v2 作为在范围 [i1, i2] 区域中的最小最大值.// while(i1i2) {int v1 Integer.MAX_VALUE, v2 Integer.MIN_VALUE;ci1i1; ci2i2;for (int i i1; i i2; i) {if(array[i] v2) {v2 array[i];ci2 i;} if(array[i] v1) {v1 array[i];ci1 i;}}System.out.println(v1 v1 , v2 v2);i1 ci11;i2 ci2-1; counter 2;}if(i1i2) {counter;} }
}
【4】O(nlgn)的时间复杂度的思路是利用分治思想下面给出伪代码但源码未实现仅供参考// input: [10, 9, 2, 5, 3, 7, 101, 18]
// output: [2, 3, 7, 101]// 此题的分治版本.(伪代码源码未实现)
class MinMax {int i1; // 最小值的对应indexint i2; // 最大值的......public MinMax(int i1, int i2) {this.i1 i1;this.i2 i2;}public MinMax(){}
}
public class NiBiNuRecursion {static int counter 0;static MinMax result;public static void main(String[] args) {int[] array {10, 90, 76, 12, 25, 78, 99, 177, 132, 156};find(array, 0, array.length-1);System.out.println(result counter);}// 分治算法.static MinMax find(int[] array, int i1, int i2) {if(i1i2) {int center (i1i2)/2;MinMax a find(array, i1, center);MinMax b find(array, center1, i2);merge(...); // 这里应该要做一次merge.} else return new MinMax(i1,i1);return result;}
}
