找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 904|回复: 1
收起左侧

[资源分享] 31 Almost Sorted Array

[复制链接]

48

主题

5

精华

383

积分

高级会员

Rank: 3Rank: 3

积分
383

最佳新人

发表于 6-2-2015 07:54 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

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)



  1.     // https://www.hackerrank.com/challenges/almost-sorted
  2.     public static boolean isAlmostSorted(int [] a) {
  3.         if(a.length == 0)   return true;
  4.         int left = 0, right = a.length - 1;
  5.         // try to store swap region as far as possible
  6.         for(int i=1; i<a.length; i++) {
  7.             if(a[i-1] == a【i】)  left = i-1; // store leftmost
  8.             else if(a[i-1] > a【i】) {
  9.                 if((a[i-1] != a[left]))
  10.                     left = i - 1;
  11.                 break;
  12.             }
  13.         }
  14.         for(int j=a.length-2; j>=0; j--) {
  15.             if(a[j] == a[j+1])  right = j+1;    // store rightmost
  16.             else if(a[j] > a[j+1]) {
  17.                 if(a[right] != a[j+1])
  18.                     right = j + 1;
  19.                 break;
  20.             }
  21.         }

  22.         while(left <= right) {
  23.             if(a[left] > a[right])
  24.                 swap(a, left, right);
  25.             left++;
  26.             right--;
  27.         }

  28.         // check if sorted
  29.         for(int i=1; i<a.length; i++) {
  30.             if(a[i-1] > a【i】) {
  31.                 return false;
  32.             }
  33.         }

  34.         return true;
  35.     }

  36.     private static void swap(int[] a, int left, int right) {
  37.         int tmp = a[left];
  38.         a[left] = a[right];
  39.         a[right] = tmp;
  40.     }
复制代码


1

主题

0

精华

2

积分

新米人

Rank: 1

积分
2
发表于 11-24-2015 06:02 PM | 显示全部楼层
感觉这个题目描述有点confusing啊,我最开始理解成可以使用两次operation呢(两种operation每个各一次)。后来看了答案才知道是只能使用either in the following operations.
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表