用Java中的一个循环解决codingBat“evenOdd”

Question

问题是如何用Java中的codingBat解决这个问题。

问题陈述：

返回一个数组，该数组包含与给定数组完全相同的数字，但要重新排列，以便所有偶数都排在所有奇数之前。除此之外，数字可以是任意顺序。您可以修改并返回给定数组，也可以创建新数组。

偶数（{1，0，1，0，0，1，1}）→ {0, 0, 0, 1, 1, 1, 1}

偶数奇数（{3,3,2}）→{2,3,3}

偶数奇数（{2,2,2}）→{2,2,2}

这个问题很简单，有2个循环，我试图用1来解决它，但它太长了，我相信，有没有其他有效的方法来解决上述问题，使用1循环？不要使用集合！

我的解决方案：

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

boolean oddFound=false;
int count=-1;
int oddGap=0;

for(int i=0;i<nums.length;i++)
  {
     if(!(oddFound)&(nums[i]%2==0))
       continue;

       if((!oddFound)&(nums[i]%2==1))
       {
         oddFound=true;
         count=i;
         continue;
       }
       if((oddFound)&(nums[i]%2==1))
       {
         oddGap++;
         continue;
       }
        if((oddFound)&(nums[i]%2==0)) 
        {
         int temp=nums[count];
         nums[count]=nums[i];  
         nums[i]=temp;

         if(i>0)
             i--;

            if(oddGap>0)
            {
              oddGap--;
              count+=1;
              oddFound=true;
              continue;
             } 
             oddFound=false;
        } 

     }
     return nums;    

}

Answer 1

好的！我终于跳过了这个问题，这个问题实际上是关闭的，但是asker的解决方案几乎是存在的，除了在我修复的2种情况下失败：

我对asker的代码进行了注释，这使得它在几个案例中失败，如问题所示。

我认为以下是最简单、最优化的解决方案：

public int[] evenOdd(int[] nums) {
int y=nums.length,x,a=0;
int temp=0;

for(x=0;x<y;x++)
{
    if(nums[x]%2==0) {
    if(a>(y-2))
       return nums;
    else{
    //nums[a]=nums[a]+nums[x];
    //nums[x]=nums[a]-nums[x];
    //nums[a]=nums[a]-nums[x];

    temp=nums[a];
    nums[a]=nums[x];
    nums[x]=temp;
    a+=1; 
        }

    } 

    return nums; 

    }

Answer 2

您不需要任何临时列表或数组，因为您可以在原地对元素重新排序。

这是一个简单的算法：

1. 定义两个指针，左指针和右指针（最初设置为数组的边界）
2. 只要left不超过right，且nums[left]为偶数，则向左递增
3. 只要right不超过left，并且nums[right]为奇数，则向右递减
4. 如果left仍然小于right，则在left和right位置交换元素
5. 只要left仍然小于right，就重复2、3、4

知道了？以下是一些代码：

public int[] evenOdd(int[] nums) {
    // (1)
    int left = 0;
    int right = nums.length -1;
    do {
        // (2)
        while (left < right && nums[left] % 2 == 0)
            left += 1;
        // (3)
        while (right > left && nums[right] % 2 != 0)
            right -= 1;
        // (4)
        if (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
    } while (left < right);   // (5)
    return nums;
}

Answer 3

由于可以创建一个新数组，而且数字的顺序与此无关，因此我将使用以下方法：

public int[] evenOdd(int[] nums) {
    int[] output = new int[nums.length];
    int evenPos = 0;
    int oddPos = nums.length-1;
    for (int i : nums) {
        if (i%2==0) {
            output[evenPos++]=i;
        } else {
            output[oddPos--]=i;
        }
    }

    return output;
}

更新：一个不太可读的版本，不需要额外的数组（按照@Seelenvirtuose的建议，只是没有额外的循环）

public int[] evenOdd(int[] nums) {
    int evenPos = 0;
    int oddPos = nums.length-1;
    while (true) {
        if (evenPos>=oddPos || evenPos>=nums.length || oddPos<0) {
            break;
        }

        if (nums[evenPos]%2==0) {
            evenPos++;
        }
        if (nums[oddPos]%2!=0) {
            oddPos--;
        }

        if (evenPos<oddPos && nums[evenPos]%2 != 0 && nums[oddPos]%2 == 0) {
            int tmp = nums[evenPos];
            nums[evenPos] = nums[oddPos];
            nums[oddPos] = tmp;

            oddPos--;
            evenPos++;

        }
    }
    return nums;
}