Codingbat fix45有更简单的解决方案吗？

Question

我试图解决这个CodingBat问题:

(这是一个稍微难以修复的版本问题.)返回一个包含与给定数组完全相同的数字的数组,但重新排列,以便每4个后面紧跟一个5.不要移动4,而是每隔一个数字可能会动.该数组包含相同数量的4和5,并且每4个数字后面的数字不是4.在此版本中,5可能出现在原始数组中的任何位置.

fix45({5, 4, 9, 4, 9, 5}) ? {9, 4, 5, 4, 5, 9}
fix45({1, 4, 1, 5}) ? {1, 4, 5, 1}
fix45({1, 4, 1, 5, 5, 4, 1}) ? {1, 4, 5, 1, 1, 4, 5}

我最初使用的方法通过了所有的网站测试,但我认为它不适用于更长的数组.初始方法使用了2个循环并且没有使用新数组.我已经创建了一个引入新数组和第三个嵌套循环的解决方案,我相信它将适用于所有问题实例.但是,该网站声明本节中的问题可以通过2个循环来解决,所以我想知道是否确实有一个2循环解决方案可以解决问题的任何实例.这是问题和我的3循环解决方案:

public int[] fix45(int[] nums) {

    int[] locations = {-1};

    for (int i = 0; i < nums.length - 1; ++i) {

        if (nums[i] == 4) {

            JLoop:
            for (int j = nums.length-1; j >= 0; --j) {
                if (nums[j] == 5) {
                    for (int k = locations.length-1; k>=0 ; --k) {
                        if (locations[k] == j) {
                            continue JLoop;
                        } 
                    }
                    nums[j] = nums[i + 1];
                    nums[i + 1] = 5;
                    locations[locations.length - 1] = i+1;
                    locations = java.util.Arrays.copyOf(locations,
                            locations.length + 1);
                    locations[locations.length-1] = -1;
                    break;
                }
            }
        }
    }
    return nums;

}

Answer 1

每次发现4时,从阵列的一端重新开始搜索合适的5似乎是浪费.阵列的一部分已经被扫描,并且已知不包含可以移动的5.这是O(n)时间和O(1)空间.

    public static int[] fix45(int[] nums) {

      int j = 0;
      for (int i = 0; i < nums.length - 1; ++i) {
        if (nums[i] == 4 && nums[i + 1] != 5) {
          /*
           * Need to find the next movable 5 That means an element that is 5 and
           * either is the first element or is preceded by anything other than 4
           */
          while (nums[j] != 5 || (j != 0 && nums[j - 1] == 4)) {
            j++;
          }
          nums[j] = nums[i + 1];
          nums[i + 1] = 5;
        }
      }
      return nums;
    }