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

Question

我正在尝试解决这个 CodingBat 问题：

（这是 fix34 问题的一个稍微困难的版本。）返回一个包含与给定数组完全相同的数字的数组，但重新排列，以便每个 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;

}

score 8 · Accepted Answer

每次找到 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;
    }

score 3 · Accepted Answer

使用一个额外的数组，这是一个带有“一个循环”的解决方案（没有嵌套循环的循环）：

public int[] fix45(int[] nums) {
  int[] otherValues = new int[nums.length];

  for(int i = 0, c = 0; i < nums.length; i++)
    if(nums[i] != 4 && nums[i] != 5)
      otherValues[c++] = nums[i];

  for(int i = 0, c = 0; i < nums.length; i++)
    if(nums[i] == 4)
      nums[++i] = 5;
    else
      nums[i] = otherValues[c++];

  return nums;
}

我们修复四点，取出非四点和非五点，然后将所有值按顺序放回原处。

为了提高空间使用率（可能不会太多），您可以在制作额外数组之前计算四的数量。

score 1 · Accepted Answer

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

 int t=0;
  for(int i=0; i< nums.length ; i++)
     for(int j=0;j<nums.length ; j++)

     if(nums[i]==5 && nums[j]==4)
     {
      t=nums[j+1];
      nums[j+1]=nums[i];
      nums[i]=t;
     }
     return nums;
}

score 0 · Accepted Answer

以下方法将使用 O(n) 空间在 O(n) 时间内运行：

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

    if (nums == null || nums.length <= 1) {
        return nums;
    }

    // store all the 5s pos
    int[] pos = new int[nums.length];
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 5) {
            pos[j++] = i;
        }
    }

    j = 0;
    for (int i = 0; i <= nums.length - 2; i++) {
        if (nums[i] == 4 && nums[i + 1] != 5) {
            if (j >= pos.length) {
                System.err
                        .println("No more 5s: there are more 4 than 5 in the input array");
                break;
            }
            // fix45 swapping
            nums[pos[j++]] = nums[i + 1];
            nums[i + 1] = 5;
        }
    }

    return nums;

}

score 0 · Accepted Answer

public int[] fix45(int[] nums) {
  int idx4 = -1;
  int idx5 = -1;
  while (true) {
    while (true) { // find a 4 without a 5 after it
      idx4 = find(nums, 4, ++idx4);
      if (idx4 == -1)  // done if no more 4's
        return nums;
      if (nums[idx4+1] != 5)
        break;
    }
    while (true) { // find a 5 without a 4 before it
      idx5 = find(nums, 5, ++idx5);
      if (idx5 == 0 || nums[idx5-1] != 4)
        break;
    }
    nums[idx5] = nums[idx4+1];  // swap the 4 and 5
    nums[idx4+1] = 5;
  }
}

public int find(int[] nums, int num, int start) {
  for (int i = start; i < nums.length; i++)
    if (nums[i] == num)
      return i;
  return -1;

score 0 · Accepted Answer

修复 dansalmos 备注后：

public int[] fix45(int[] nums) {
    for (int i = 0; i < nums.length; i++) {

        if (nums[i] == 4) {
            if(nums[i+1] == 5) continue;

            for( int j = 0; i < nums.length; j++){
                if(nums[j] == 5 && (j==0 || nums[j-1] != 4)){
                    nums[j] = nums[i+1];
                    nums[i+1] = 5;
                    break;
                }
            }

        }
    }

    return nums;
}

score 0 · Accepted Answer

public int[] fix45(int[] nums) {
   if (nums.length < 2) {
   return nums;
   }
        int index = 0;
        int index2 = 0;
        int index3 = 0;
        int[] only5 = fives(nums);
        int[] after4 = new int[count4(nums)];
        for (int a = 0; a < nums.length - 1; a++) {
            if (nums[a] == 4) {
                after4[index] = nums[a + 1];
                index++;
                nums[a + 1] = only5[index2];
                index2++;
            }
        }
//This while loop gets the frst number that is not a 5 that is after a 4
        while (nums[0] == 5) {
            nums[0] = after4[index3];
            index3++;
        }

        if (nums[nums.length - 2] != 4 && nums[nums.length - 1] == 5) {
            nums[nums.length - 1] = after4[index3];
            index3++;
        }
        for (int b = 1; b < nums.length; b++) {
            if (nums[b] == 5 && nums[b - 1] != 4) {
                nums[b] = after4[index3];
                index3++;
            }
        }
        return nums;
    }
    public int count4(int[] nums) {
        int cnt = 0;
        for (int e : nums) {
            if (e == 4) {
                cnt++;
            }
        }
        return cnt;
    }
    public int[] fives(int[] nums) {
        int index = 0;
        int[] only5 = new int[count4(nums)];
        for (int e : nums) {
            if (e == 5) {
                only5[index] = e;
                index++;
            }
        }
        return only5;
    }

//长解，向上滚动

score 0 · Accepted Answer

我意识到这个线程已有多年历史，但我只想添加我的解决方案：

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

    int notAFourOrFive = 0;

    int[] ary = new int[nums.length];

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 4) {
            ary[i] = 4;
            ary[i+1] = 5;
        }
        else if (nums[i] != 5) {
            notAFourOrFive = nums[i];
        }
    }

    for (int j = 0; j < ary.length; j++) {
        if (ary[j] == 0) {
            ary[j] = notAFourOrFive;
        }
    }

    return ary;
}

看到4s 和5s 的数量相等，只要4找到 a 就可以安全地将它们添加到新数组中。在这种情况下使用它是安全的i+1，因为 a4永远不会出现在数组的末尾。4每当达到非或非时，设置“其他”数字也是安全的5，因为在每个测试中所有其他数字都是相同的。

score 0 · Accepted Answer

这是简单的答案:)

 public int[] fix45(int[] nums) {
  int p5=0;//tracker for 5's

  for(int i=0;i<nums.length;i++){
    if(nums[i] == 4){// got a 4 
      for(int j = p5 ;j<nums.length;j++){
        //finding a 5 for that 4 at nums[i]
        if(nums[j] == 5 && ( (j > 0 && nums[j-1]!=4 ) || (j==0) )){
          // found 5 and checking if it is not preceded by a 4      
          //swap if not preceded by a 4
          int temp = nums[i+1];
          nums[i+1] = nums[j];
          nums[j] = temp;

          p5 = j;//set the tracker to where we found 5 for nums[i]
          break;//break out of loop
        }
      } 
    }
  }

  return nums;

}

score 0 · Accepted Answer

此解决方案使用 LinkedHashSet。我认为时间的 O 表示法是O(n)，空间也是O(n)。

  public int[] fix45(int[] nums) {
  Set<Integer> ind4 = new LinkedHashSet<>();
  Set<Integer> ind5 = new LinkedHashSet<>();

  //Store positions for all fours and fives except those fives
  //that immediately follow number four.
  for (int i = 0; i < nums.length; ++i) {
    if (nums[i] == 4){
      ind4.add(i);
      if (i + 1 < nums.length && nums[i + 1] == 5){
        i++;
      } 
    }else if (nums[i] == 5){
      ind5.add(i);
    } 
  } 

  Iterator<Integer> iter5ind = ind5.iterator();

  for (Integer i : ind4){
    if (i + 1 > nums.length || !iter5ind.hasNext()) break;
    if (nums[i + 1] == 5){
      continue;
    }
    int j = iter5ind.next();

    int tmp = nums[i + 1];
    nums[i + 1] = nums[j];
    nums[j] = tmp;
  }
  return nums;
}

score 0 · Accepted Answer

我只想添加我的解决方案，到目前为止，我在 CodingBat 上进行了测试并通过了所有测试，并且没有使用 2 个 for 循环

    public int[] fix45(int[] nums) {
        if (nums.length == 0 || nums.length == 1 || nums.length == 2) {
            return nums;
        }

        int indexof4 = 0, indexof5 = 0;
        int indexToWorkonForRplcmnt = -1;
        while (indexof4 < nums.length && indexof5 < nums.length) {
            if ((indexof4 + 1) < nums.length && nums[indexof4] == 4 && nums[indexof4 + 1] != 5) {
                indexToWorkonForRplcmnt = indexof4 + 1;
//                System.out.println("IndexOf4:"+indexToWorkonForRplcmnt);

            } else {
                indexof4++;
            }

            if ((indexof5) < nums.length && nums[indexof5] == 5) {

                if (indexof5 == 0 && nums[indexof5] == 5) {
//                    System.out.println("IndexOf5:"+indexof5);
                } else if (nums[indexof5 - 1] != 4 && nums[indexof5] == 5) {
//                    System.out.println("IndexOf5:"+indexof5);
                } else {
                    indexof5++;
                }

            } else {
                indexof5++;
            }

            if (indexToWorkonForRplcmnt != -1 && (indexof5) < nums.length && nums[indexof5] == 5) {
                System.out.println("IndexOf4:" + indexToWorkonForRplcmnt);
                System.out.println("IndexOf5:" + indexof5);
                int temp = nums[indexToWorkonForRplcmnt];
                nums[indexToWorkonForRplcmnt] = nums[indexof5];
                nums[indexof5] = temp;
                indexToWorkonForRplcmnt = -1;
                indexof4++;
                indexof5++;
            }

        }
        return nums;
    }

score 0 · Accepted Answer

public int[] fix45(int[] nums) {
    int[] array = new int[nums.length];
    int temp = 0;

    for (int i = 0; i < array.length; i++) {
          if (nums[i]==4) {
              array[i] = 4;
              array[i+1]= 5;
          }
    }

    for (int i = 0; i < array.length; i++) {
        if (nums[i]!=4 && nums[i]!=5) {
            temp = nums[i];
            }
        for (int j = 0; j < array.length; j++) {
            if (array[j]==0) {
                array[j]=temp;
            }
        }


    }

    return array;
}

score 0 · Accepted Answer

这里有很多复杂的代码。我认为我们这样简化：

public int[] fix45(int[] nums) {        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 4) {
                for (int j = 0; j < nums.length; j++) {
                    if (nums[j] == 5) {
                        if (j > 0 && nums[j - 1] != 4) {
                            int tmp = nums[i + 1];
                            nums[i + 1] = 5;
                            nums[j] = tmp;
                        } else if (j == 0) {
                            int tmp = nums[i + 1];
                            nums[i + 1] = 5;
                            nums[j] = tmp;
                        }
                    }
                }
            }
        }
        return nums;
    }

score 0 · Accepted Answer

它也可以在一个while循环中完成！

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


      int start = 0;
      int end = nums.length-1;

      boolean is4 = false;
      boolean is5 = false;


      while( start < nums.length ){

        if(nums[start] == 4 && nums[start+1]!=5){
          is4 = true;
        }

        if(nums[end] == 5 && (end == 0 || (end-1>=0 && nums[end-1]!=4))){
          is5 = true;
        }


        if(is4 && is5){
          int temp = nums[start+1];
          nums[start+1] = nums[end];
          nums[end] = temp;

          is4 = false;
          is5 = false;
          end = nums.length-1;
        }



        if(is4){
          end--;
          continue;
        }

        start++;
      }
      return nums;


    }

score 0 · Accepted Answer

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

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

        if (nums[i] == 5 && i == 0 || nums[i] == 5 && nums[i - 1] != 4) {

            int a5 = i;

            for (int j = 0; j < nums.length; j++) {

                if (nums[j] == 4 && nums[j + 1] != 5) {

                    int temp = nums[j + 1];

                    nums[j + 1] = 5;
                    nums[a5] = temp;

                    break;
                }

            }

        }
    }

    return nums;

}

score 0 · Accepted Answer

public int[] fix45(int[] nums) 
{
    for(int i=0; i<nums.length; i++)
    {
        if(nums[i]==5)
        {
            for(int j=0; j<nums.length; j++)
            if(nums[j]==4&&nums[j+1]!=5)
            {
                f(nums, i, j+1);
            }
        }
    }
    return nums;
}
///this "helper" function swaps 2 elements of the array
public void f(int []nums , int m, int n)
{
    int t= nums[m];
    nums[m] =nums[n];
    nums[n] = t;
}

score 0 · Accepted Answer

这是我发现的一个简单的解决方案。只需创建跟踪 4 和 5 的 ArrayList，然后交换值。这怎么容易理解？

public int[] fix45(int[] nums) 
{
        //Create a copy array to manipulate and eventually return.
        int[] ret = nums;
        //Create two ArrayLists that let us track for and five positions.
        ArrayList<Integer> fourPositions = new ArrayList<Integer>();
        ArrayList<Integer> fivePositions = new ArrayList<Integer>();
        //Get the positions of fours and fives and add them to their respective ArrayLists.
        for (int i = 0; i < ret.length; i++)
        {
          if (ret[i] == 4)
          {
            fourPositions.add(i);
          }
          if (ret[i] == 5)
          {
            fivePositions.add(i);
          }
        }
        //Swap all of the places right after the fours with a respective number of the fives,
        for (int i = 0; i < fourPositions.size(); i++)
        {
          int temp = ret[fourPositions.get(i) + 1];
          ret[fourPositions.get(i) + 1] = ret[fivePositions.get(i)];
          ret[fivePositions.get(i)] = temp;
        }
        //Return the array.
        return ret;
 }

score 0 · Accepted Answer

import java.util.Arrays;

public class Fix45 {
    public static void main(String[] args) {
        assertArrays(new int[]{9, 4, 5, 4, 5, 9}, new int[]{5, 4, 9, 4, 9, 5});
        assertArrays(new int[]{1, 4, 5, 4, 5}, new int[]{5, 4, 5, 4, 1});
        assertArrays(new int[]{1, 1, 4, 5, 4, 5}, new int[]{5, 5, 4, 1, 4, 1});
        assertArrays(new int[]{4, 5, 4, 5, 1}, new int[]{4, 5, 4, 1, 5});
        assertArrays(new int[]{4, 5, 4, 5, 2}, new int[]{4, 2, 4, 5, 5});
    }

    public static int[] fix45(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == 4 && nums[i + 1] != 5){

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

                    if(nums[j] == 4 && nums[j + 1] == 5){
                        j++;
                        continue;
                    }
                    if (nums[j] == 5) {
                        int temp = nums[j];
                        nums[j] = nums[location];
                        nums[location] = temp;
                    }
                }
            }
        }
        return nums;
    }


    private static void assertArrays(int[] expected, int[] input) {
        int[] actual = fix45(input);
        System.out.println(Arrays.toString(actual));
        boolean status = Arrays.equals(expected, actual);
        System.out.println(status);
    }
}

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

18 回答 18

Related

Reference