Is there a simpler solution for Codingbat fix45?

Question

I am trying to solve this problem with CodingBat:

(This is a slightly more complicated version of fix34.) Return an array that contains exactly the same numbers as the given array but is rebuilt, so every 4 immediately follows 5. Do not move 4, but any other number can move. The array contains the same number 4 and 5, and each 4 has a number after it, which is not 4. In this version, 5 can appear anywhere in the original array.

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} 

At first I used a method that passed all the site tests, but I do not think that it will work for longer arrays. The original method used 2 loops and did not use a new array. I created a solution that introduces a new array and a third nested loop, and I believe that this will work for all instances of the problem. However, the site states that the problems in this section can be solved with 2 cycles, so I wonder if there really is a 2-loop solution that will work for any problem. Here is the question and my solution with three loops:

 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

Restarting the search for a suitable 5 from one end of the array every time 4 is found seems wasteful. Part of the array has already been scanned and, as you know, does not contain 5 that can be moved. This is O (n) time and O (1) space.

  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; } 

Answer 2

Using an additional array, here is a one-cycle solution (loops without nested loops):

 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; } 

We fix the fours, take out not four and non-fifths, but return all the values ​​in order.

To improve the use of space (perhaps not by much), you can count the number of four before creating an additional array.

Answer 3

 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; } 

Answer 4

Correct after Dansalmos remarks:

 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; } 

Answer 5

The following method will execute in O (n) time using O (n) space:

 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; } 

Answer 6

 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; 

Answer 7

 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; } 

// long solution, scroll up

Answer 8

I understand that this topic is years old, but I just wanted to add my solution:

 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; } 

If the number of 4 and 5 is equal, it is safe to add them to the new array whenever 4 found. In this case, it is safe to use i+1 , because 4 never comes to the end of the array. It is also safe to set a “different” number whenever not 4 or 5 reached, because all other numbers are the same in every test.

Answer 9

 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; } 

Answer 10

  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; } 

Answer 11

Here is a simple solution that I found. Just create ArrayLists that track 4 and 5 and change the values. How easy is it to understand?

 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; } 

Answer 12

This solution uses LinkedHashSet. I think the O-notation for time is O (n), and for space also 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; } 

Answer 13

 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); } } 

Answer 14

There is so much complicated code here. I think we simplified like this:

 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; } 

Answer 15

I just want to add My Solution as I tested on CodingBat and passed all tests without using 2 for loops

  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; }