如何从数组中找到第n个重复项

Question

我正在尝试解决这个问题。

基本上，我需要从字符数组中选择第二个重复项。

Input {'x','y','z','x','y'} output: y
Input { 'a', 'a', 'b', 'a', 'c', 'b', 'a', 'c', 'b' } Output: b
Input { 'a','a','a','b','a','c','b','a','c','b' } output: b

EDIT:

Input {'a', 'b', 'c', 'b', 'a', 'c', 'b', 'a', 'c', 'b'} Output: a

我已经尝试编写这段代码，但是如果第一个字符立即重复，它会失败 :( 请帮我纠正一下？

 public static char returnSecondDuplicate(char[] arr)
        {
            if (arr.Length == 0)
                throw new ArgumentNullException("empty input");
            var dictionary = new Dictionary<char, int>();
            Char second = '\0';
            int duplicateCount = 0;

            for (int i = 0; i <= arr.Length - 1; i++)
            {

                if (!dictionary.ContainsKey(arr[i]))
                {
                    dictionary.Add(arr[i], 1);
                }
                else
                {
                    duplicateCount++;

                    if (duplicateCount == 2)
                    {
                        second = arr[i];
                    }
                }
            }

            return second;
        }

- Navyseal

---

你的计数仅仅是在增加，没有与任何特定元素相连接。 - MaD

在您的第三个输入中，以 { 'a'，'a'，'a'，... 开头的那些，第二个重复项不应该是 'a' 吗？因为它出现了多次。您想选择第二个重复项，但是要选择与第一个不同的值的那个？ - AlvaroAV

是的，你说得对。我试图查看.ElementAt（0）并比较重复项是否为第一个重复项，但不知何故还缺少一些额外的检查。仍然无法通过for循环获取它 :( - Navyseal

Answer 1

这应该很好地解决了问题：

var secondDuplicate = input.GroupBy( c => c)
                           .Where( g => g.Count() > 1)
                           .Skip(1)
                           .First()
                           .Key;

首先将它们分组，然后将只有一个元素的组打折扣（因为它们不是重复项），然后取第二个元素（跳过第一个）。

- Øyvind Bråthen

---

如果你使用FirstOrDefault()然后立即获取Key，那么如果没有第二个重复项，仍然会抛出异常。你可以将其更改为First()（这样可以更早地抛出更有用的错误信息），或者加入一个空值检查（如果没有第二个重复项不是一个异常情况）。 - Tim S.

是的，我同意。应该让它更加健壮，以处理那些没有第二个副本的情况。 - Øyvind Bråthen

代码在这个输入 {'a', 'b', 'c', 'b', 'a', 'c', 'b', 'a', 'c', 'b'} 上失败了。在这种情况下，输出应该是 'a'，因为 'b' 是第一个重复项，而 'a' 是第二个重复项。 - Navyseal

这不会找到真正的第二个重复项，即要匹配两次的第一个字符。 - James

@James 和 Navyseal - 我按照我实际认为他想要的结果解决了它。不是完全清楚他想要第一个完整的重复，还是最先开始的重复。可以从两个方面进行争论，但现在我们知道OP已经澄清了，似乎逻辑必须被修改以考虑这一点。 - Øyvind Bråthen

Answer 2

这是一个通用的扩展方法，适用于以下情况：

public static T GetNthDuplicate<T>(this IEnumerable<T> source, int n)
{
    HashSet<T> hashSet = new HashSet<T>();
    return source.Where(item => !hashSet.Add(item))
                 .Distinct().Skip(n - 1) //one based index
                 .FirstOrDefault();
}

- Ufuk Hacıoğulları

Answer 3

问题在于你正在计算所有重复项的数量，而不是单个字符的重复项数量。

一些linq答案已经被提出，但如果你想知道如何修复你现有的代码，你可以像这样做：

public static char returnSecondDuplicate(char[] arr)
{
    if (arr.Length == 0)
        throw new ArgumentNullException("Empty Array passed");
    var dictionary = new Dictionary<char, int>();
    char firstDuplicate = '\0';

    for (int i = 0; i <= arr.Length - 1; i++)
    {

        if (!dictionary.ContainsKey(arr[i]))
        {
            dictionary.Add(arr[i], 1);
        }
        else if (firstDuplicate == '\0')
        {
            firstDuplicate = arr[i];
        }
        else if(arr[i] != firstDuplicate)
        {
            return arr[i];
        }

    }

    return '\0'; //not found
}

基本上，你需要跟踪哪个字母是第一个重复的。一旦你有了第一个重复的字母，就要检查后续的字母是否相同。第一个不同的重复字母就是你想要返回的。

- mao47

Answer 4

你原始代码的问题在于每次看到重复字符时都会增加计数器，但是你并没有检测它是否已经被计入。一个简单的改变是使用列表（而不是整数）来跟踪重复项。

此外，另一个小优化（在我看来）是使用while循环而不是for循环，因为你只想要迭代直到满足某些条件，所以它似乎更适合。

public static char returnSecondDuplicate(char[] arr)
{
    if (arr.Length == 0)
        throw new ArgumentNullException("Empty Array passed");
    var dictionary = new Dictionary<char, int>();
    var duplicates = new List<char>();
    Char second = '\0';
    int i = 0;

    while (duplicates.Count != 2 && dictionary.Count != arr.Length)
    {
        if (!dictionary.ContainsKey(arr[i]))
            dictionary.Add(arr[i], 1);
        else if (!duplicates.Contains(arr[i]))
            duplicates.Add(arr[i]); // only add duplicates once (ignoring any duplicate duplicates!)

        second = duplicates.Count == 2 ? arr[i] : second;
        i++;
    }

    return second;
}

查看运行情况

- James