使用數組的奇數之前的偶數和只有一個循環

我試圖解決這個問題。我沒有得到正確的解決方案。請幫助。使用數組的奇數之前的偶數和只有一個循環

問題：返回一個包含與給定數組完全相同的數字但重新排列的數組，以便所有偶數都出現在所有奇數之前。除此之外，數字可以按任何順序排列。您可以修改並返回給定的數組，或者創建一個新的數組。
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

使用數組的奇數之前的偶數和只有一個循環

回答

相關問題