技术需求：在数组中查找重复数字并仅输出最后一个重复项

Got it, let's tackle this problem where we need to find the last occurring duplicate number in an array. To be clear: we're looking for a number that appears more than once, and among all such duplicates, it's the one whose final occurrence is later than any other duplicate's final occurrence.

Approach 1: Traverse from the End (Most Efficient) #

The fastest way to nail this is to iterate the array from right to left, keeping track of elements we've already seen. The first element we encounter that's already in our "seen" set is our answer—since we're going backwards, this is the last duplicate in the original array.

Here's a Java implementation:

import java.util.HashSet;
import java.util.Set;

public class LastDuplicateFinder {
    public static int findLastDuplicate(int[] arr) {
        // Handle edge case: array too short to have duplicates
        if (arr == null || arr.length < 2) {
            throw new IllegalArgumentException("Array must have at least two elements to contain duplicates");
        }

        Set<Integer> seenElements = new HashSet<>();
        // Traverse from the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int current = arr[i];
            if (seenElements.contains(current)) {
                return current; // Found our last duplicate!
            }
            seenElements.add(current);
        }

        // If we finish traversing and no duplicates exist
        throw new IllegalArgumentException("No duplicate numbers found in the array");
    }

    public static void main(String[] args) {
        int[] example1 = {1,2,2,3,4,3,5};
        System.out.println(findLastDuplicate(example1)); // Output: 3

        int[] example2 = {2,2};
        System.out.println(findLastDuplicate(example2)); // Output: 2
    }
}

• Time Complexity: O(n) — we iterate through the array once, and set operations (add/contains) are average O(1).
• Space Complexity: O(n) — in the worst case, we store all elements in the set before finding a duplicate.

Approach 2: Frequency Map + Reverse Traversal #

If you need to keep track of element frequencies for other purposes, this approach works too. First, we count how many times each element appears, then traverse the array backwards to find the first element with a frequency greater than 1.

Java code for this method:

import java.util.HashMap;
import java.util.Map;

public class LastDuplicateFinder {
    public static int findLastDuplicateWithFrequency(int[] arr) {
        if (arr == null || arr.length < 2) {
            throw new IllegalArgumentException("Array must have at least two elements to contain duplicates");
        }

        Map<Integer, Integer> frequencyMap = new HashMap<>();
        // First pass: count occurrences of each element
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Second pass: find the last element with frequency > 1
        for (int i = arr.length - 1; i >= 0; i--) {
            if (frequencyMap.get(arr[i]) > 1) {
                return arr[i];
            }
        }

        throw new IllegalArgumentException("No duplicate numbers found in the array");
    }

    public static void main(String[] args) {
        int[] example1 = {1,2,2,3,4,3,5};
        System.out.println(findLastDuplicateWithFrequency(example1)); // Output: 3
    }
}

• Time Complexity: O(n) — two linear passes through the array.
• Space Complexity: O(n) — the frequency map stores all unique elements.

Edge Cases to Consider #

• Arrays with only two identical elements (like {2,2}) — should return that element.
• Arrays with no duplicates — you'll want to handle this (throw an exception, return a sentinel value like -1, etc., based on your requirements).
• Arrays with multiple duplicates (like {5,3,5,3,5}) — should return 5, since its last occurrence is later than 3's.

内容的提问来源于stack exchange，提问作者Vishal Kumar