我需要一种算法来查找在ArrayList中只出现一次的最大数字。
例如，假设我有一个包含元素的ArrayList<Integer>
[3, 3, 3, 6, 7, 8, 8, 9, 9, 9] .
在这里，我需要的算法将生成数字7，因为它是列表中最大的未重复数字。
前提 条件：
-
不保证输入列表可以排序。
-
输入列表将始终包含至少一个非重复数字。
如果我们假设输入列表是排序的，我们应该能够在 O(N) 中执行此操作，不需要额外的空间。
public static Integer maxUnduplicatedVal(ArrayList<Integer> lst){
if(lst == null || lst.isEmpty())
return null;
if(lst.size() == 1) return lst.get(0);
if(! lst.get(lst.size() - 1).equals(lst.get(lst.size() - 2)))
return lst.get(lst.size() - 1);
for(int i = lst.size() - 2; i > 0; i--){
Integer next = lst.get(i + 1);
Integer here = lst.get(i);
Integer prev = lst.get(i - 1);
if(! next.equals(here) && ! prev.equals(here)) return here;
}
if(! lst.get(0).equals(lst.get(1))) return lst.get(0);
return null; //All duplicates
}
如果并不总是排序，最快的方法是创建列表的副本，然后删除重复项，然后调用 max 函数 Collections .制作副本是一个非常好的主意 - getter真的不应该改变他们收到的收藏。（这包括对给定集合进行排序）。
private static List<Integer> getUniques(List<Integer> list) {
HashMap<Integer, Boolean> flagMap = new HashMap<>();
//Total Loop: O(N)
for(Integer i : list){
if(flagMap.containsKey(i)) flagMap.put(i, false); //O(1)
else flagMap.put(i, true); //O(1)
}
ArrayList<Integer> result = new ArrayList<Integer>();
//Total Loop: O(N)
for(Integer i : list){
if(flagMap.get(i)) result.add(i); //O(1)
}
return result;
}
public static Integer maxUnduplicatedVal(ArrayList<Integer> lst){
List<Integer> lstCopy = getUniques(lst);
return Collections.max(lstCopy);
}
这仍然是O(N)的，但有一些额外的空间要求。
Collections.frequency 可能在这里有用...
Integer[] myArr = {3, 3, 3, 6, 7, 8, 8, 9, 9, 9}; // sample array
ArrayList<Integer> myList = new ArrayList<Integer>(Arrays.asList( myArr ) );
// creating a set from an ArrayList will remove any duplicate elements
HashSet<Integer> mySet = new HashSet<Integer>(myList);
/* Make sure list isn't empty or null here, etc. */
Integer largest = null;
// iterate through the set, ensuring you don't examine duplicates
for ( Integer i : mySet ) {
// if the frequency of that element is 1, we can compare it
if ( Collections.frequency(myList, i) == 1 )
{
if ( largest == null )
{
largest = i; // base case
} else if ( i > largest ) {
largest = i;
}
}
}
System.out.println( "The largest non-duplicate is " + largest );
// or return, etc.
这里是算法
1） 如果列表尚未排序，则首先执行 Collections.sort（list）
2）从最后一个开始，因为它是最大的数字并获取其索引
3）检查该索引处的数字是否等于索引-1处的数字，如果是，则它是最大的重复数，其他明智的做法是对索引-1重复此步骤
最好的方法是在元素列表的排序数组中找到未重复的元素。因此，通过这样做，我们可以隔离未重复元素的列表，然后我们可以在获得的列表中找到最大的元素。
建议参考下面的链接以获取更多详细信息。
在排序数组中查找未重复的元素
-布鲁斯