在排序數組中查找範圍內屬性的項目？

我有一個基於年齡字段升序排序的Obj類數組。我需要在O（log（N））時間內找到數組中具有給定最小和最大年齡的Obj項目的數量。在排序數組中查找範圍內屬性的項目？

我不認爲我可以使用binarySearch，因爲.equals只有當名稱和年齡都相同時才爲true。

這是我迄今爲止所做的，但我不確定複雜性是什麼。

public class Obj { 
    private String name; 
    private int age; 

    private Obj(String name, int age) { 
     if (name == null) { 
      throw new IllegalArgumentException(); 
     } 
     this.name = name; 
     this.age = age; 
    } 

    public String getName() { 
     return name; 
    } 

    public int getAge() { 
     return age; 
    } 

    public boolean equals(Object o) { 
     if (!(o instanceof Obj)) { 
      return false; 
     } 

     Obj other = (Obj) o; 
     return name.equals(other.getName()) && age == other.getAge(); 
    } 

    public static Obj[] loadFromFile(File f) { 
     // Loads from file and returns an array of Obj 
    } 
} 

public static int getObjCountInRange(Obj[] a, int minAge, int maxAge) { 
    if(a == null || (minAge < 0 || maxAge < 0) || (minAge > maxAge)) { 
     throw new IllegalArgumentException(); 
    } 

    int start = 0; 
    for(int i = 0; i < a.length; i++) { 
     if(a[i].getAge() >= minAge) { 
      start = i; 
      break; 
     } 
    } 

    int end = 0; 
    for(int i = a.length -1; i > 0; i--) { 
     if(a[i].getAge() <= maxAge) { 
      end = i; 
      break; 
     } 
    } 

    return (end - start) + 1; 
}

來源

2013-03-06 Jack

那麼最新的問題？ – Aashray 2013-03-06 10:14:34

@Aashray我相信OP需要幫助編寫一個算法，該算法可以在O（Log n）時間複雜度的排序數組中找到兩點之間的值。 – christopher 2013-03-06 10:15:55

沒有什麼能夠阻止你查看代碼behing Collections.binarySearch，複製它並修改它以便與你的字段進行比較...... 所有你真正需要的是用minAge（O（log（N））查找值，find maxAge（O（log（N）再次）的值，然後它們之間的值的子集是你的結果 – radai 2013-03-06 10:17:10

寫比較器並使用比較器對數組進行排序。

然後使用第二個二進制搜索簽名，它將比較器與您的新比較器一起找到您的上限和下限。

如果你沒有得到完全匹配，你會得到一個負數，這表明你的價值將在哪裏，如果找到，反轉這個，你有你開始/結束價值的位置你的邊界條件。

來源

2013-03-06 10:25:14

恩，這個數組已經排序了，爲什麼要使用它？ – eis 2013-03-06 10:25:57

我不確定它已經按照我們用於識別邊界條件的字段進行了排序。如果它已經按該字段排序，則不排序，這將是多餘的。 – 2013-03-06 10:28:50

這個問題與here相同，在那裏我給出了O（logn）的實現。

該想法是通過範圍二進制搜索的下界和上界。舉個例子，所有的價值都在談論年齡的價值。

來源

2013-12-20 12:55:39 herohuyongtao

在排序數組中查找範圍內屬性的項目？

回答

相關問題