7

私はこのCodingBatの問題を解決しようとしています：

（これは、fix34問題の少し難しいバージョンです。）指定された配列とまったく同じ番号を含むが、4ごとに5が続くように再配置された配列を返します。4を移動せず、1つおきの番号を移動します。動くかもしれません。配列には同じ数の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つのループを使用し、新しい配列を使用しませんでした。新しい配列と3番目のネストされたループを導入するソリューションを作成しましたが、問題のすべてのインスタンスで機能すると思います。ただし、このセクションの問題は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;

}
4

18 に答える 18

8

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;
    }
于 2012-11-12T03:05:48.950 に答える
3

追加の配列を使用して、「1つのループ」（ネストされたループのないループ）を使用したソリューションを次に示します。

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

4を修正し、4以外と5以外を取り出し、値をすべて元に戻します。

スペースの使用量を改善するために（おそらくそれほどではありませんが）、追加の配列を作成する前に4の数を数えることができます。

于 2012-11-12T03:06:01.603 に答える
1 
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;
}
于 2014-07-15T06:48:38.137 に答える
0

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;
}
于 2012-11-12T02:38:51.720 に答える
0

次のメソッドは、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;

}
于 2012-11-12T03:05:31.120 に答える
0 
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;
于 2013-12-20T16:47:00.827 に答える
0 
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;
    }

//長い解決策、上にスクロール

于 2015-04-05T16:20:02.413 に答える
0

このスレッドは古いものだと思いますが、ソリューションを追加したかっただけです。

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とsの量が等しいので、aが見つかったときは5いつでもそれらを新しい配列に追加しても安全です。この場合、配列の最後に決して来ることはないため、4安全に使用できます。他のすべての番号は各テストで同じであるため、非または非に到達するたびに「その他」の番号を設定することも安全です。i+1445

于 2015-04-16T17:06:58.960 に答える
0 
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;
}
于 2016-03-11T02:30:18.950 に答える
0 
     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;

}
于 2016-08-23T14:15:44.563 に答える
0

これが私が見つけたうまくいく簡単な解決策です。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;
 }
于 2016-12-31T04:27:54.123 に答える
0

このソリューションはLinkedHashSetを使用します。時間のO表記はO（n）であり、空間のO表記も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;
}
于 2018-12-27T17:13:16.453 に答える
0 
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);
    }
}
于 2019-01-29T07:56:52.757 に答える
0

ここには非常に多くの複雑なコードがあります。私たちはこのように単純化したと思います：

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;
    }
于 2019-05-19T22:50:28.087 に答える
0

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;
    }
于 2019-09-19T00:39:42.797 に答える
0

ここに簡単な答えがあります:)

 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;

}
于 2019-11-08T04:14:10.727 に答える
0

1つの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;


    }
于 2020-03-30T13:45:10.493 に答える
0 
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;
}
于 2020-05-27T19:28:29.243 に答える