排序未排序數組中的正整數

這是在最近的編程訪談中給我的。我得到一個未排序的具有負值和正值的整數數組，並且需要對它們進行排序，但僅限於正值。我想知道您的一些解決方案可能不使用Google。排序未排序數組中的正整數

回家後我發現Arrays.sort（）按升序對數組排序，但我不確定如何輸出到只有正值的新數組，因爲這是一個要求。如果它們大於-1，我可以通過打印來打印它們，但是如何將它們輸入到新數組中，而無需遍歷數組並計算正數值的數量以獲取新數組的大小，然後實例化新的數組，然後循環再次將它們添加到新的數組..這種解決方案似乎不是最佳的，有沒有更好的方法？

輸出需要一個新的數組，只有正面的價值觀，即排序

下面是我到目前爲止有：

import java.util.Arrays; 


    public class Test { 

     public static void main(String[] args) { 
      // TODO Auto-generated method stub  
      int[] unsorted = { 
       -3, 95, -4, 20, 5, 6, 8 
      }; 
      int[] sorted = unsorted; 
      Arrays.sort(sorted); 

      for (int s: sorted) { 
       if (s > -1) 
        System.out.println(s); 
      } 
     } 

    }

來源

2014-01-24 Eduardo Dennis

你在說什麼聽起來像過濾+排序。「輸出到只有正值的新陣列」。你是否想要一個只有正值的新數組，這是排序的。或者你的意思是你想要一個既有負值也有正值的新數組，但只有正值被排序。 – crush

該問題未被詳細說明。什麼_「排序但僅限於正值」_是什麼意思？ –

對我而言，這聽起來像面試問題的目的是檢查，看看你是否真正理解排序的過程。這在面試中很重要，因爲編寫自定義排序邏輯在許多編程職位中經常發生。 – crush

你可以嘗試把數據在PriorityQueue，並確保只能處理正值：

int[] unsorted = { -3, 95, -4, 20, 5, 6, 8 }; 

PriorityQueue<Integer> q = new PriorityQueue<>(unsorted.length); 

for (int a : unsorted) { 
    if (a > 0) 
     q.add(a); 
} 

while (!q.isEmpty()) { 
    System.out.println(q.poll()); 
}

這種做法將是O（n日誌（n））的其中ñ是數組中正整數的個數。相反，排序整個陣列將是O（nlog（n））其中n是整個陣列的長度。

來源

2014-01-24 22:50:59 arshajii

你在哪裏得到O（nlog（n））？優先級隊列的Javadoc表示_Implementation注意：這個實現提供了入侵和出列方法的O（log（n））時間。 – Rainbolt

重複給出_O（n log（n））_的優先級隊列_n_次的_O（log（n））_。這只是一個僞裝的堆排序。 – chuckj

@chuckj是的，這是絕對正確的。 – arshajii

在Java中，Collection.sort必須穩定的，所以如果你使用一個比較器來表示所有的負數相等，但是對於正數來說，你所期望的是，你會得到你所需要的。

來源

2014-01-24 22:42:50

迭代數組
對於每一個正值，位置和價值存儲到兩個陣列
排序值數組

來源

2014-01-24 22:52:49 Leo

爲什麼你需要步驟（4）？你想要的值不是數組的值嗎？ – chuckj

因爲負面的也很重要:-)他們爲什麼說呢？ – Leo

愛德華在修改後的問題中明確表示他們不是。 – chuckj

如果有什麼你對你的分類執行二進制搜索0數組，然後只從那一點打印值？ Arrays.binarySearch()返回0在您的數組中找不到0的指數。

import java.util.Arrays; 

public class Test { 

    public static void main(String[] args) {  
     int[] unsorted = { 
      -3, 95, -4, 20, 5, 6, 8 
     }; 
     int[] sorted = unsorted; 
     Arrays.sort(sorted); 

     int breakingPoint = Arrays.binarySearch(sorted, 0); 
     for (int i = breakingPoint; i < sorted.length; i++) { 
      System.out.println(sorted[i]); 
     } 
    } 

}

來源

2014-01-24 22:58:43 Rainbolt

這有一個問題，'n'是原始數組的大小，而不是'n'是排序的'O（n log n）'的正整數的數目。對於少數負數不是什麼大問題，但對於大型陣列來說是個大問題。 – chuckj

現在我想到了，你是對的。減少n進行排序會更有效率，即O（nlog（n）），並且對於檢查正數是大的，即O（n）。不過，我會留下這個答案，因爲你提供了一些有價值的見解。 – Rainbolt

您應該制定自己的排序算法。我會使用修改後的快速排序在接受採訪時：

1挑0是第一個遞歸調用的支點，把那些正確的陣列

2只通話等於或大於0的所有號碼在第一次遞歸調用的右側數組上使用快速排序，對於其他遞歸調用，使用隨機數據透視表。

3-連接時，刪除找到的第一個0。

快速（nlogN），即使在同一個數組中，也可以做到，或返回一個新的。

來源

2014-01-24 22:58:55

其實你不需要步驟（3），因爲第一步已經告訴你在哪裏停止。這也聽起來像是面試官要回答的問題。 – chuckj

mmm，是的，只要主鍵不爲0，他就可以保持連接。 –

僅爲動態方面創建列表意味着可能會在刪除過程中多次調整陣列的大小。

我選擇改爲使用Arrays.copyOf調整陣列的大小後，我知道它需要多大。

我做的第一件事是過濾掉負面：

int[] unsorted = { 
    -3, 95, -4, 20, 5, 6, 8 
}; 

int[] positives = new int[unsorted.length]; //It can only be as big as unsorted. 

int i = 0, j = 0; 

for (; i < unsorted.length; i++) { 
    if (unsorted[i] >= 0) 
     positives[j++] = unsorted[i]; 
}

然後，我調整陣列：

positives = Arrays.copyOf(positives, j);

最後，我對它進行排序：

Arrays.sort(positives);

這裏是IDEOne.com demo

來源

2014-01-24 23:06:09 crush

請對您的決定進行評論，並對此答案進行倒票。 – crush

簡單分隔正數 - 它需要一個副本

List<Integer> positives = new ArrayList<Integer>(); 
for (Integer number: unsorted) { 
    if (number > 0) { 
     positives.add(number); 
    } 
}

，然後對其進行排序。

Collections.sort(positives);

來源

2014-01-25 03:03:34 kanbagoly

排序未排序數組中的正整數

回答

相關問題