|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
很坑的一题,主要注意元素相等时的判断。
思路是,分别从左边和右边扫描数组,找到第一个违反sort规则的元素。如果这个元素有重复,则要找最左和最右的那个元素。
另外,reverse可以归结到swap。所以找到最左和最右的那个元素,就swap中间的元素。最后再检查一遍看看swap后的是不是有序即可。
提供几个test case:
// int[] a = {2,2,10,2};
// int[] a = {2,2,10,2,2};
// int[] a = {1,2,1,2,2};
// int[] a = {1,1,3,3,3};
// int[] a = {3,3,2,2};
// int[] a = {3,2,2};
// int[] a = {};
都应该返回true
时间复杂度O(n)
- // https://www.hackerrank.com/challenges/almost-sorted
- public static boolean isAlmostSorted(int [] a) {
- if(a.length == 0) return true;
- int left = 0, right = a.length - 1;
- // try to store swap region as far as possible
- for(int i=1; i<a.length; i++) {
- if(a[i-1] == a【i】) left = i-1; // store leftmost
- else if(a[i-1] > a【i】) {
- if((a[i-1] != a[left]))
- left = i - 1;
- break;
- }
- }
- for(int j=a.length-2; j>=0; j--) {
- if(a[j] == a[j+1]) right = j+1; // store rightmost
- else if(a[j] > a[j+1]) {
- if(a[right] != a[j+1])
- right = j + 1;
- break;
- }
- }
- while(left <= right) {
- if(a[left] > a[right])
- swap(a, left, right);
- left++;
- right--;
- }
- // check if sorted
- for(int i=1; i<a.length; i++) {
- if(a[i-1] > a【i】) {
- return false;
- }
- }
- return true;
- }
- private static void swap(int[] a, int left, int right) {
- int tmp = a[left];
- a[left] = a[right];
- a[right] = tmp;
- }
复制代码
|
|