按順序排列偶數和奇數

我試圖在一次通過時分別將偶數和奇數分別分離到左側和右側。此外，我想確保這些數字按照順序排序，這樣整個邏輯將具有O（n）的複雜性。按順序排列偶數和奇數

例如，如果我的輸入是{9,8,2,3,11,10,1};

這個邏輯我實現了o/p爲{10 8 2 3 11 9 1}，但我想確保我的輸出在同一遍中排序爲{2,8,10,1,3,9,11} 。

static void segregateEvenOdd(int arr[]) { 
    /* Initialize left and right indexes */ 
    int left = 0, right = arr.length - 1; 
    while (left < right) { 
     /* Increment left index while we see 0 at left */ 
     while (arr[left] % 2 == 0 && left < right) 
      left++; 

     /* Decrement right index while we see 1 at right */ 
     while (arr[right] % 2 == 1 && left < right) 
      right--; 

     if (left < right) { 
      /* Swap arr[left] and arr[right] */ 
      int temp = arr[left]; 
      arr[left] = arr[right]; 
      arr[right] = temp; 
      left++; 
      right--; 
     } 
    } 
}

來源

2016-01-20 skanda

你的問題究竟是什麼？ – Skam

對O（n）中的數組進行排序 - 你不是要求太多嗎？ –

給定的數組是否已經排序？ –

使用比較整數排序算法最好的算法中能做到這一點的O(nlgn)這樣你就可以用比較整數排序不能達到O(n)。

你可以做什麼是：你可以使用非比較整數排序算法。像：

這將整理您的O(n)與你輸入一些條件陣列。查看更多細節的例子。

來源

2016-01-20 06:41:21

這是不可能的一次。你真的有兩種不同的種類。一個用於偶數，另一個用於賠率。

這是我會建議的。

解決方法1.

，如果你被允許引入新的數據結構採取以下方法創建兩個的ArrayList（一個連一個的奇）他們適當地分開。兩個都運行Collections.Sort。以迭代方式重新初始化您的初始數組。

解決方案2.

使用你上面妥善獨立埃文斯和賠率的方法。統計列表中的平均數。構建一個典型的排序例程，比如mergesort，並在數組的兩個不同的段上調用例程。上面的例子可以這樣調用

merge(arr, 0, 2); 
merge(arr, 3, 6);

這兩種解決方案都具有整體時間複雜度：O（nlogn）。空間複雜度：O（n）。解決方案一更容易實施，但解決方案二允許您進行更多就地排序。其他排序例程的最佳情況是O（n）時間，但不保證它。

來源

2016-01-20 09:42:58

我會用一個快速排序或其它任何標準算法，但限定元件之間的比較爲：a小於b如果a是偶數和b是奇數還是它們都是偶數或奇數和a<b。

這不會給你O（n），這是不可能的，但通過重用已知的算法可以達到最佳性能。

來源

2016-01-20 11:46:33 manuBriot

使用Sort overload可讓您通過Comparator。比較函數應該像下面這樣（僞代碼）：

Comparison(a, b) 
{ 
    if (Even(a) && !Even(b)) 
     return -1; // a < b 
    if (Even(b) && !Even(a)) 
     return 1; // a > b 
    // both are even, or both are odd. 
    if (a < b) return -1; 
    if (a > b) return 1; 
    return 0; 
}

來源

2016-01-20 15:31:34

按順序排列偶數和奇數

回答

相關問題