一千萬個為什麽

搜索

如何對兩個整數數組進行順序不敏感比較

我想要以這種方式比較的Java代碼(例如):

<1 2 3 4>  = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>

我不能使用hashmap表或任何東西;只是沒有庫的純代碼。

我知道有兩種方法。

  1. sort them and compare the array index by index
  2. use two for loops and compare the outer index with the inner index. I have been trying with this but still not working:

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {   
            if(a[i] != a[j] && j == n)
                return false;
        }
    }
    return true;
    

代碼有什麽問題嗎?謝謝

最佳答案

Sort & compare. You can't get the complexity better than that, and any "improvement" that you do on the speed comes at the risk that your code will be wrong.

[編輯]實際上......如果你知道你的數字相對較小(例如:數組只包含0到1000之間的數字),那麽在O(n)中有另一種選擇。這樣的事情(抱歉,如果語法錯誤,我最近沒有使用java):

int count[1001];//already intialized to 0

for(int i=0;i<=1000 && arrays_identical; i++)
    arrays_identical &= count[i]==0;

免責聲明:此代碼不包含“健全性檢查”(即數組實際上長度為“n”,數字在規定的間隔內) - 它只是為了說明原理。

轉載註明原文: 如何對兩個整數數組進行順序不敏感比較