在 ArrayList 中找到最大的不重复数

Question

我需要一个算法来找出在 ArrayList 中只出现一次的最大数字。

例如，假设我有一个 ArrayList<Integer> 元素

[3, 3, 3, 6, 7, 8, 8, 9, 9, 9].

在这里，我需要的算法会产生数字 7，因为它是列表中最大的不重复数字。

先决条件：

输入列表不保证排序。
输入列表将总是包含至少一个非重复数字。

Answer 1

最好的方法是在元素列表的排序数组中找到不重复的元素。因此通过这样做我们可以分离不重复元素的列表，然后我们可以在获得的列表中找到最大的。

建议参考下面的 link 了解更多详情。

Find the unduplicated element in a sorted array

-布鲁斯

Answer 2

如果我们假设输入列表已排序，我们应该能够在 O(N) 中执行此操作，无需额外 space。

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
}

如果它并不总是排序，最快的方法是创建列表的副本，然后删除重复项，然后只调用Collections中的max函数。制作副本是一个非常好的主意 - getters 真的不应该改变他们收到的集合。（这包括对给定的集合进行排序）。

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)，尽管有一些额外的 space 要求。

Answer 3

这是算法

1) 首先执行 Collections.sort(list) 如果列表尚未排序

2)从最后一个开始，因为它是最大的数，得到它的索引

3) 检查该索引处的数字是否等于索引-1 处的数字，如果是，则它是最大的重复数字，否则对索引-1 重复此步骤

Answer 4

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.

在 ArrayList 中找到最大的不重复数

Find the largest unduplicated number in an ArrayList

java

sorting

algorithm

for-loop

compare