1. Introduction

1.导言

In this tutorial, we’ll explore the problem of finding the first non-repeating element in a list. We’ll first understand the problem statement and then implement a few methods to achieve the desired outcome.

在本教程中，我们将探讨查找列表中第一个不重复元素的问题。我们将首先了解问题的陈述，然后使用几种方法来实现所需的结果。

2. Problem Statement

2 问题陈述

Given a list of elements, the task is to find the first element that doesn’t repeat in the list. In other words, we need to identify the first element that appears only once in the list. If there are no non-repeating elements, we then return an appropriate indication, e.g., null.

给定一个元素列表，我们的任务是找到列表中第一个不重复的元素。换句话说，我们需要找出第一个在列表中只出现一次的元素。如果没有不重复的元素，我们就会返回一个适当的指示，例如空。

3. Using for Loop

3.使用 for 循环

This method uses nested for loops to iterate through the list and check for repeating elements. It’s straightforward but less efficient.

该方法使用嵌套的 for 循环遍历列表并检查重复元素。这种方法简单明了，但效率较低。

3.1. Implementation

3.1 实施

First, we iterate through each element in the input list. For each element, we checks if it appears only once in the list by iterating through the list again. If an element is found to be repeating, we set the flag isRepeating to true. If an element is found to be non-repeating, the method returns that element.

首先，我们遍历输入列表中的每个元素。对于每个元素，我们会再次遍历列表，检查它是否在列表中只出现过一次。如果发现元素重复出现，我们会将标记 isRepeating 设置为 true。如果发现元素不重复，该方法将返回该元素。

Below is the implementation of the above idea:

以下是上述想法的实现过程：

Integer findFirstNonRepeating(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        int current = list.get(i);
        boolean isRepeating = false;
        for (int j = 0; j < list.size(); j++) {
            if (i != j && current == list.get(j)) {
                isRepeating = true;
                break;
            }
        }
        if (!isRepeating) {
            return current;
        }
    }
    return null; 
}

Let’s walk through an example list:

让我们来看一个列表示例：

[1, 2, 3, 2, 1, 4, 5, 4]

During the first iteration, the inner loop scans through the entire list to look for any other occurrence of element 1. It finds another occurrence of element 1 at index 4. Since element 1 appears again elsewhere in the list, it’s considered repeating. The process is repeated for element 2. In the third iteration, it doesn’t find any other occurrence of element 3 in the list. Hence, it’s identified as the first non-repeating element, and the method returns 3.

在第一次迭代中，内循环扫描整个列表，查找元素 1 的任何其他出现。它在索引 4 处找到了元素 1 的另一次出现。由于元素 1 在列表的其他位置再次出现，因此它被视为重复出现。对元素 2 重复上述过程。在第三次迭代中，它没有在列表中找到元素 3 的任何其他出现。因此，它被认定为第一个非重复元素，该方法返回 3。

3.2. Complexity Analysis

3.2.复杂性分析

Let n be the size of the input list. The outer loop iterates through the list once, resulting in O(n) iterations. The inner loop also iterates through the list once for each outer loop iteration, resulting in O(n) iterations for each outer loop iteration. Therefore, the overall time complexity is O(n^2). The approach uses a constant amount of extra space, regardless of the size of the input list. Hence, the space complexity is O(1).

设 n 为输入列表的大小。外循环对列表迭代一次，迭代次数为 O(n)。内循环在每次外循环迭代时也对列表进行一次迭代，因此每次外循环迭代的迭代次数为 O(n)。因此，总体时间复杂度为 O(n^2)。无论输入列表的大小如何，该方法都会使用恒定数量的额外空间。因此，空间复杂度为 O(1)。

This method provides a straightforward solution to find the first non-repeating element. However, it has a time complexity of O(n^2), making it inefficient for large lists.

该方法为查找第一个非重复元素提供了一个直接的解决方案。但是，它的时间复杂度为 O(n^2)，因此对于大型列表来说效率很低。

4. Using indexOf() and lastIndexOf()

4.使用 indexOf() 和 lastIndexOf()

The indexOf() method retrieves the index of the first occurrence of an element, while lastIndexOf() returns the index of the last occurrence. By comparing these indices for each element in the list, we can identify elements that appear only once.

indexOf() 方法检索元素首次出现的索引，而 lastIndexOf() 返回元素最后一次出现的索引。通过比较列表中每个元素的这些索引，我们可以识别只出现过一次的元素。

4.1. Implementation

4.1.实施

In the iteration, we check if each element’s first occurrence index isn’t equal to its last occurrence index. If they aren’t equal, it means the element appears more than once in the list. If an element is found with the same first and last occurrence indices, the method returns that element as the first non-repeating element:

在迭代过程中，我们会检查每个元素的首次出现索引是否与其最后出现索引不相等。如果不相等，则表示该元素在列表中出现不止一次。如果发现一个元素的首次出现索引和最后出现索引相同，该方法就会将该元素作为第一个非重复元素返回：

Integer findFirstNonRepeatedElement(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        if (list.indexOf(list.get(i)) == list.lastIndexOf(list.get(i))) {
            return list.get(i);
        }
    }
    return null;
}

Let’s walk through the provided example list:

让我们浏览一下提供的示例列表：

[1, 2, 3, 2, 1, 4, 5, 4]

During the initial iteration, both indexOf(1) and lastIndexOf(1) return 0 and 4. They aren’t equal. This indicates that element 1 is a repeating element. This process is repeated for subsequent element 2. However, when examining element 3, both indexOf(3) and lastIndexOf(3) return 2. This equality implies that element 3 is the first non-repeating element. Therefore, the method returns 3 as the result.

在初始迭代期间，indexOf(1) 和 lastIndexOf(1) 都返回 0 和 4。它们不相等。这表明元素 1 是一个重复元素。随后的元素 2 将重复这一过程。但是，在检查元素 3 时，indexOf(3) 和 lastIndexOf(3) 都返回 2。这种相等性意味着元素 3 是第一个不重复的元素。因此，该方法返回 3 作为结果。

4.2. Complexity Analysis

4.2.复杂性分析

Let n be the size of the input list. The method iterates through the list once. For each element, it calls both indexOf() and lastIndexOf(), which may iterate through the list to find the indices. Therefore, the overall time complexity is O(n^2). This approach uses a constant amount of extra space. Hence, the space complexity is O(1).

设 n 为输入列表的大小。该方法在列表中遍历一次。对于每个元素，它都会调用 indexOf() 和 lastIndexOf()，这两个函数可能会遍历列表以查找索引。这种方法会使用一定量的额外空间。因此，空间复杂度为 O(1)。

While this approach provides a concise solution, it’s inefficient due to its quadratic time complexity (O(n^2)). For large lists, especially with repeated calls to indexOf() and lastIndexOf(), this method may be significantly slower compared to other approaches.

虽然这种方法提供了一个简洁的解决方案，但由于其二次方时间复杂度（O(n^2)）而效率低下。对于大型列表，尤其是重复调用 indexOf() 和 lastIndexOf() 时，这种方法可能比其他方法慢得多。

5. Using HashMap

5.使用 HashMap

In another way, we can use a HashMap to count occurrences of each element and then find the first non-repeating element. This approach is more efficient than the simple for loop method.

另一种方法是，我们可以使用 HashMap 来计算每个元素的出现次数，然后找到第一个不重复的元素。这种方法比简单的 for 循环方法更有效。

5.1. Implementation

5.1.实施

In this method, we iterate through the input list to count the occurrences of each element and store them in the HashMap. After counting the occurrences, we iterate through the list again and check if the count of each element is equal to 1. If the count is equal to 1 for any element, it returns that element as the first non-repeating element. If no non-repeating element is found after iterating through the entire list, it returns -1.

在此方法中，我们遍历输入列表，计算每个元素的出现次数，并将其存储到 HashMap 中。计算出现次数后，我们再次遍历列表，检查每个元素的计数是否等于 1。如果任何元素的计数等于 1，则返回该元素作为第一个非重复元素。如果在遍历整个列表后没有找到非重复元素，则返回 -1。

Below is the implementation of the above idea:

以下是上述想法的实现过程：

Integer findFirstNonRepeating(List<Integer> list) {
    Map<Integer, Integer> counts = new HashMap<>();

    for (int num : list) {
        counts.put(num, counts.getOrDefault(num, 0) + 1);
    }
    
    for (int num : list) {
        if (counts.get(num) == 1) {
            return num;
        }
    }
    
    return null;
}

Let’s walk through the provided example list:

让我们浏览一下提供的示例列表：

[1, 2, 3, 2, 1, 4, 5, 4]

The counts after the first iteration will be:

第一次迭代后的计数将是

{1=2, 2=2, 3=1, 4=2, 5=1}

When iterating through the list, 1 and 2 have counts greater than 1, so they aren’t non-repeating. Element 3 has a count of 1, so it’s the first non-repeating element.

当遍历列表时，1 和 2 的计数大于 1，因此它们不是非重复元素。元素 3 的计数为 1，因此它是第一个非重复元素。

5.2. Complexity Analysis

5.2.复杂性分析

Let n be the size of the input list. Counting occurrences of each element in the list takes O(n) time. Iterating through the list to find the first non-repeating element also takes O(n) time. Therefore, the overall time complexity is O(n). This approach uses additional space proportional to the number of unique elements in the input list. In the worst case, where all elements are unique, the space complexity is O(n).

设 n 为输入列表的大小。计算列表中每个元素的出现次数需要 O(n) 秒。遍历列表以找到第一个不重复的元素也需要 O(n) 时间。因此，总体时间复杂度为 O(n)。这种方法使用的额外空间与输入列表中唯一元素的数量成正比。在所有元素都是唯一的最坏情况下，空间复杂度为 O(n)。

This method provides an efficient solution to finding the first non-repeating element in a list for a wide range of input data. It utilizes a HashMap to keep track of element occurrences, which significantly improves the performance compared to the traditional for loop approach.

该方法提供了一种高效的解决方案，可为各种输入数据查找列表中的第一个非重复元素。它利用 HashMap 来跟踪元素的出现，与传统的 for 循环方法相比，该方法显著提高了性能。

6. Using Array as Frequency Counter

6.将阵列用作频率计

This method uses an array as a frequency counter to count occurrences of each element and find the first non-repeating element.

这种方法将数组用作频率计数器，对每个元素的出现次数进行计数，并找出第一个不重复的元素。

6.1. Implementation

6.1.实施

At first, we initialize an array frequency of size maxElement + 1, where maxElement is the maximum element in the list. We iterate through the list, and for each element num, increment frequency[num]. This step ensures that frequency[i] stores the count of occurrences of the element i.

首先，我们初始化一个大小为 maxElement + 1 的数组 frequency，其中 maxElement 是列表中的最大元素。我们遍历列表，对每个元素 num 递增 frequency[num]。这一步骤可确保 frequency[i] 存储元素 i 的出现次数。

Next, we iterate through the list again. For each element num, we check if frequency[num] is equal to 1. If frequency[num] is 1, we return num as it’s the first non-repeating element:

接下来，我们再次遍历列表。对于每个元素 num，我们都要检查 frequency[num] 是否等于 1。如果 frequency[num] 是 1，我们将返回 num ，因为它是第一个不重复的元素：

Integer findFirstNonRepeating(List<Integer> list) {
    int maxElement = Collections.max(list);
    int[] frequency = new int[maxElement + 1];

    for (int num : list) {
        frequency[num]++;
    }
    
    for (int num : list) {
        if (frequency[num] == 1) {
            return num;
        }
    }

    return null;
}

Let’s walk through the provided example list:

让我们浏览一下提供的示例列表：

[1, 2, 3, 2, 1, 4, 5, 4]

We initialize the frequency array with all elements set to zero:

我们对频率数组进行初始化，将所有元素设置为零：

[0, 0, 0, 0, 0, 0]

We iterate through the list:

我们对列表进行遍历：

Increment frequency[1] to 2.
Increment frequency[2] to 2.
Increment frequency[3] to 1.
Increment frequency[4] to 2.
Increment frequency[5] to 1.

Next, we iterate through the list again, for frequency[1] and frequency[2] the value is 2, so it’s not non-repeating. For frequency[3], the value is equal to 1, so the method returns 3.

接下来，我们再次遍历列表，对于frequency[1]和frequency[2]，值是2，因此不是不重复。对于frequency[3]，值等于1，因此该方法返回 3。

6.2. Complexity Analysis

6.2.复杂性分析

Let n be the size of the input list. We iterate through the list twice, but each iteration provides a time complexity of O(n). This approach is more memory-efficient than the HashMap approach, with a space complexity of O(maxElement).

假设 n 是输入列表的大小。我们对列表进行两次迭代，但每次迭代的时间复杂度为 O(n)。这种方法比 HashMap 方法更节省内存，其空间复杂度为 O(maxElement)。

This approach is particularly efficient when the range of elements in the list is small because it avoids the overhead of hashing and provides a more straightforward implementation. However, if the input list contains negative numbers or zero, the frequency array must cover the entire range of possible elements, including negative numbers if applicable.

当列表中的元素范围较小时，这种方法尤其有效，因为它避免了散列的开销，并提供了更直接的实现。但是，如果输入列表中包含负数或零，频率数组必须覆盖整个可能的元素范围，包括负数（如果适用）。

7. Summary

7.摘要

Here’s a comparison table for the different implementations:

下面是不同实现方式的对照表：

Method	Time Complexity	Space Complexity	Efficiency	Suitable for Large Lists
Using for Loop	O(n^2)	O(1)	Low	No
Using indexOf()	O(n^2)	O(1)	Low	No
Using HashMap	O(n)	O(n)	High	Yes
Using Array Counter	O(n)	O(maxElement)	High	No

8. Conclusion

8.结论

In this article, we learned a few approaches to finding the first non-repeating element in a list, each with its advantages and considerations. While each method offers its advantages and considerations, the HashMap approach stands out for its efficiency in identifying the first non-repeating element. By leveraging HashMaps, we can achieve optimal performance.

在本文中，我们学习了几种查找列表中第一个不重复元素的方法，每种方法都有其优点和注意事项。虽然每种方法都有自己的优势和注意事项，但 HashMap 方法在识别第一个非重复元素方面的效率非常突出。利用 HashMap，我们可以获得最佳性能。

As always, the source code for the examples is available over on GitHub.

与往常一样，这些示例的源代码可在 GitHub 上获取。