使用数组的奇数之前的偶数和只有一个循环

我试图解决这个问题。我没有得到正确的解决方案。请帮助。使用数组的奇数之前的偶数和只有一个循环

问题：返回一个包含与给定数组完全相同的数字但重新排列的数组，以便所有偶数都出现在所有奇数之前。除此之外，数字可以按任何顺序排列。您可以修改并返回给定的数组，或者创建一个新的数组。
evenOdd([1, 0, 1, 0, 0, 1, 1]) → [0, 0, 0, 1, 1, 1, 1] 
evenOdd([3, 3, 2]) → [2, 3, 3] 
evenOdd([2, 2, 2]) → [2, 2, 2] 

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

    int l = nums.length; 

    if(l<2) 
    return nums; 

    int j=l-1; 
    for(int i=0;i<l;i++) 
    { 
    if(nums[i]%2==1) 
    { 
     while(j>i && nums[j]%2!=0) { 
      j--; 
     }   
     int t=nums[i]; 
     nums[i]=nums[j]; 
     nums[j]=t; 

     j--;   
    } 
    } 
    return nums; 
}

来源

2016-10-04 Abhishek Sharma

在你的例子中，你正在使用2个循环（用于和while），你在标题中说明你只能使用一个循环？那么你需要什么？ – Asoub

@Abhishek Sharma：请看看我的O（N）时间和O（1）空间复杂度解决方案...... –

这基本上是quicksort的分区算法。你只需要将分区应用一次。 –

作为阵列的顺序并不重要，你只需要一个循环，你可以试试下面的功能，

public int[] evenOdd(int[] nums) { 
    if (nums.length < 2) return nums; 

    int[] result = new int[nums.length]; 
    int even = 0; 
    int odd = nums.length - 1; 

    for (int i = 0; i < nums.length; i++) { 
     if (nums[i] % 2 == 0) 
      result[even++] = nums[i]; 
     else 
      result[odd--] = nums[i]; 
    } 
    return result; 
}

来源

2016-10-04 13:43:42

非常感谢Shaishav！ –

不知道这是“欺骗”，但你可以创建2个阵列，1至持有唇上和1持有胜算。在循环中，您可以将每个值的所有数字复制到它们的偶数或奇数数组，然后在循环之后，将数组加入/合并到一个新数组中并返回新数组。

来源

2016-10-04 12:17:22 raphael75

这可以工作，但你需要的内存量增加了三倍。 – aquinas

你实际上超级密切。如果你只是换这个代码，您有：

int t = nums[i]; 
nums[i] = nums[j]; 
nums[j] = t; 
j--;

内的，如果

if (j > i)

你的代码实际工作。

来源

2016-10-04 13:10:29 aquinas

谢谢aquinas。你能否告诉我们这个问题是否可以用一个循环来解决？ –

如果性能是不是太重要，你可以使用流：

static int[] evenOdd(int[] nums) { 
    return Arrays.stream(nums) 
      .boxed() 
      .sorted(Comparator.comparingInt(i -> i % 2)) 
      .mapToInt(i -> i) 
      .toArray(); 
}

不幸的是，IntStream没有一个sorted方法，它接受Comparator（仅一个，这就是为什么你必须框和拆箱使用Stream.sorted(Comparator)。

来源

2016-10-04 14:12:23 xehpuk

这是一个需要O(N)时间和O(1)空间来完成您的任务的代码。我为Python代码表示歉意。

arr = list(map(int, raw_input().split())) 

i = 0 
j = len(arr) - 1 

while i<j: 
    if arr[i]%2 != 0 and arr[j]%2 == 0: 
     t = arr[i] 
     arr[i] = arr[j] 
     arr[j] = t 
     i = i + 1 
     j = j -1 

    elif arr[i]%2 == 0 and arr[j]%2 == 0: 
     i = i + 1 

    elif arr[i]%2 == 0 and arr[j]%2 != 0: 
     j = j - 1 

    else: 
     j = j - 1 

print arr

说明：代码逻辑是相当自我解释。我们有两个计数器，从左端开始的i和从右端开始的j。如果左边的计数器指向一个even那么我们只是增加它，因为它在正确的位置。 [请记住你想将平衡转移到左边。所以这甚至已经在数组的左侧，所以我们只增加i]。请查看代码逻辑，以根据偶数或奇数元素上的当前指针找出要采取的操作。

例如：

如果我们发现i指向一个odd和j指向一个`偶数，那么我们交换和移动两个指针。这是可以理解的，我希望

上面的解决方案是就地，需要O（1）空间和O（N）时间...希望这有助于！

来源

2016-10-05 06:26:44

使用数组的奇数之前的偶数和只有一个循环

回答

相关问题