首页 > 代码库 > i<j<k
i<j<k
Question:
Given an array, does it exist that
i < j < k where A[i] < A[J] < [K].
// Option 1. // Brute force. // Given any index i, return true if there exists: // A[m] < A[i], m < i // A[n] > A[i], n > i boolean hasLessInLeft(int[] a, int i) { for (int index = 0 ; index < i ; index ++) { if (a[index] < a[i]) return true; } return false; } boolean hasMoreInRight(int[] a, int i) { ... } // O(n ^ 2) boolean has3Increasing(int[] a) { for (int i = 0 ; i < a.length ; i ++) { if (hasLessInLeft(a, i) && hasMoreInRight(a, i)) return true; } return false; } // A better solution? // maintain min, mid boolean has3Increasing(int[] a) { Integer min = null; Integer mid = null; for (int i : a) { if (min == null || i < min) { min = i; } else if (mid == null || i < mid) { mid = i } else if (i > mid) // This means there must be a min before mid. { return true; } } return false; }
i<j<k
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。