在数组中查找升序重复对

    public int solution(int[] A)
    {
        int N = A.Length;            
        int count = 0;
        for (int j = 0; j < N; j++)
        {
            count += FindPairs(A[j], j, A);
        }
        return count;
    }
    public int FindPairs(int item, int ci, int[] A)
    {
        int len = A.Length;
        int counter=0;
        int k = ci+1;
        while (k < len)
        {
            if (item == A[k])
                counter++;
            k++;
        }
        return counter;
    }

从您的代码中，目标似乎是返回A中升序重复对的计数。

我们观察到，如果在A中出现x的m，则值x的升序重复对的数量为m choose 2或m (m - 1) / 2。

因此，我们对每个唯一的x求出m (m - 1) / 2，给出答案。

在伪代码中，这看起来像：

count = new Dictionary();
foreach a in A {
    count[a]++;
}
total = 0;
foreach key, value in count {
    total += value * (value - 1) / 2;
}
return total;

该算法是O(N)。

最近的面试问题……以下是我所做的：

using System;
using System.Collections.Generic;
using System.Linq;
namespace Codility
{
    internal class Program
    {
        public struct Indice
        {
            public Indice(int p, int q)
            {
                P = p;
                Q = q;
            }
            public int P;
            public int Q;
            public override string ToString()
            {
                return string.Format("({0}, {1})", P, Q);
            }
        }
        private static void Main(string[] args)
        {
            //                      0 1 2 3 4 5 
            int[] list = new int[] {3,3,3,3,3,3};
            int answer = GetPairCount(list);
            Console.WriteLine("answerswer = " + answer);
            Console.ReadLine();
        }
        private static int GetPairCount(int[] A)
        {
            if (A.Length < 2) return 0;
            Dictionary<int, Dictionary<Indice, Indice>> tracker = new Dictionary<int, Dictionary<Indice, Indice>>();
            for (int i = 0; i < A.Length; i++)
            {
                int val = A[i];
                if (!tracker.ContainsKey(val))
                {
                    Dictionary<Indice, Indice> list = new Dictionary<Indice, Indice>();
                    Indice seed = new Indice(i, -1);
                    list.Add(seed, seed);
                    tracker.Add(val, list);
                }
                else
                {
                    Dictionary<Indice, Indice> list = tracker[val];
                    foreach (KeyValuePair<Indice,Indice> item in list.ToList())
                    {
                        Indice left = new Indice(item.Value.P, i);
                        Indice right = new Indice(i, item.Value.Q);
                        if (!list.ContainsKey(left))
                        {
                            list.Add(left, left);
                            Console.WriteLine("left= " + left);
                        }
                        if (!list.ContainsKey(right))
                        {
                            list.Add(right, right);
                            Console.WriteLine("'t'tright= " + right);
                        }
                    }
                }
            }

            return tracker.SelectMany(kvp => kvp.Value).Count(num => num.Value.Q > num.Value.P);
        }
    }
}

我认为这是我在c#中得到的最好的版本。

    static void Main(string[] args)
    {
        var a = new int[6] { 3, 5, 6, 3, 3, 5 };
        //Push the indices into an array:
        int[] indices = new int[a.Count()];
        for (int p = 0; p < a.Count(); ++p) indices[p] = p;
        //Sort the indices according to the value of the corresponding element in a:
        Array.Sort(indices, (k, l) =>Compare(a[k], a[l]));

        //Then just pull out blocks of indices with equal corresponding elements from indices:
        int count = 0;
        int i = 0;
        while (i < indices.Count())
        {
            int start = i;
            while (i < indices.Count() && a[indices[i]] == a[indices[start]])
            {
                ++i;
            }
            int thisCount = i - start;
            int numPairs = thisCount * (thisCount - 1) / 2;
            count += numPairs;
        }
        Console.WriteLine(count);
        Console.ReadKey();
    }
    //Compare function to return interger
    private static int Compare(int v1, int v2)
    {
        if (v2 > v1)
            return 1;
        if (v1 == v2)
            return 0;
        else
            return -1;
    }

由于排序的原因，这种方法总体上具有O（n log n）的复杂性。分组的计数是线性的。

试试这个：

    private static int GetIdenticalPairCount(int[] input)
    {
        int identicalPairCount = 0;
        Dictionary<int, int> identicalCountMap = new Dictionary<int, int>();
        foreach (int i in input)
        {
            if (identicalCountMap.ContainsKey(i))
            {
                identicalCountMap[i] = identicalCountMap[i] + 1;
                if (identicalCountMap[i] > 1)
                {
                    identicalPairCount += identicalCountMap[i];
                }
                else
                {
                    identicalPairCount++;
                }
            }
            else
            {
                identicalCountMap.Add(i, 0);
            }
        }
        return identicalPairCount;
    }

测试我的版本：

public int solution(int[] A)
{
    int N = A.Length;
    int count = 0;
    for (int j = 0; j < N - 1; j++)
        for (int i = j + 1; i < N; i++)
            if (A[i] == A[j])
                count++;
    return count;
}