需要排序的最短子数组长度
2023-03-14 09:45:32 时间
题目:给定一个无序数组长度arr,求出需要排序的最短子数组长度。如输入:arr={2,3,7,5,4,6},返回4,因为只有{7,5,4,6}需要排序。注意这儿题目是要求数组按照递增排序。
代码:
1 public class Rearrange { 2 public static int findSegment(int[] A, int n) { 3 // p1 p2为需要排序的子数组边界 4 int p1 = -1; 5 int p2 = -1; 6 int max = A[0]; 7 int min = A[n - 1]; 8 //拓展右端点:更新历史最高,只要右侧出现比历史最高低的,就应该将右边界扩展到此处 9 for (int i = 0; i < n; i++) { 10 if (A[i] > max) { 11 max = A[i]; 12 } 13 //只要低于历史高峰,就要扩展需排序区间的右端点 14 if (A[i] < max) 15 p2 = i; 16 } 17 //找左端点:更新历史最低,只要左侧出现比历史最低高的,就应该将左边界扩展到此处 18 for (int i = n - 1; i >= 0; i--) { 19 20 if (A[i] < min) { 21 min = A[i]; 22 } 23 if (A[i] > min) 24 p1 = i; 25 } 26 27 if (p1 == -1) { 28 return -1; 29 } 30 // p1 p2为需要排序的子数组边界 所以应该返回长度 p2-p1+1 31 return p2-p1+1; 32 } 33 public static void main(String[] args) { 34 int res = findSegment(new int[]{2,3,7,5,4,6}, 6); 35 System.out.println(res); // 输出 4 36 } 37 }
总结:拿到这种题目,需要仔细分析,然后发现规律,并且在分析的过程中要考虑各种测试用例,小数据、大数据、反例、边界数据、时间复杂度等等。那这道题目本身没有什么算法可言,只有自己去寻找规律解决。
相关文章
- 进击的大数据 盘点2017涅槃重生的市场
- 数据信仰兴起,谁才是这个世界上最适合我的人!
- 保护个人数据的4个数据安全的最佳实践
- 大数据冲击供应链系统的4种方式
- 大数据和云计算之间那点儿非同一般的关系
- 如何为业务收集数据并将其转化为价值
- 斐讯与思科签署合作备忘录,共创数据时代商业蓝海
- 企业如何实现对大数据的处理与分析?
- 大数据可视化——5个必须知道的工具
- 斐讯牵手思科 共创数据时代新纪元
- NFV服务保障需要大数据、小数据或兼而有之?
- 警惕大数据成了互联网的“PX项目”
- 大数据,新一轮技术革命的“支点”
- 克服大数据的五大挑战——一切答案尽在云服务
- 交通数据太庞大,不如交给可视化处理
- 数据组织的自我学习将在2018年兴起
- 遭遇成长烦恼 2017AI大数据行业回顾
- 大数据测试类型&大数据测试步骤
- 数据化,从现实世界向虚拟世界的大迁徙,是一切的归宿
- 大数据和云计算的冲突