2

Link where I got the problem from

I'm trying for a O(n²) solution to finding which elements appear more than n/k times (where n=8 in this case - so more than twice) in the given array. I believe I have the solution but I can't seem to figure out why the output (shown below) isn't [2, 3]. I know that it's element 2 at index i = 3 that appears but I figured the if (count > (arr.Length / k)) condition would've fixed that. 

int[] arr = { 3, 1, 2, 2, 1, 2, 3, 3 };
int k = 4, count = 1;

for(int i = 0; i < arr.Length; i++)
{
    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[i] == arr[j])
        {
            count++;
            if (count > (arr.Length / k))
            {
                Console.WriteLine(arr[i] + " " + i);
                count = 1;
            }
        }
    }
}

Output:

3 0

2 2

2 3
4

2 回答 2

1

The problem is that you're only resetting the count when there's a match and the count is greater than arr.Length/k. You need to reset it at the end of the inner for loop or better yet define it just before the inner for loop since it isn't needed outside of that loop. Also I'm guessing you'll want to break from that loop as soon as the count meets your condition or you'll keep writing out the same thing.

int[] arr = { 3, 1, 2, 2, 1, 2, 3, 3 };
int k = 4;

for(int i = 0; i < arr.Length; i++)
{
    int count = 1;
    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[i] == arr[j])
        {
            count++;
            if (count > (arr.Length / k))
            {
                Console.WriteLine(arr[i] + " " + i );
                break;
            }
        }
    }
}

However this will still produce results for duplicate values at other locations. For instance the array {3, 1, 2, 2, 1, 2, 3, 3, 3, 3, 3, 3} with k equal to 4 produces 3,0; 3,6; 3,7; and 3,8. Assuming you only want 3,0 then a better solution would be.

int[] arr = { 3, 1, 2, 2, 1, 2, 3, 3 };
int k = 4;    

var results = arr.Select((x,i) => new {Value = x, Index = i})
    .GroupBy(x => x.Value)
    .Where(grp => grp.Count() > arr.Length / k)
    .Select(grp => grp.First());

foreach(var r in results)
{
    Console.WriteLine($"{r.Value} {r.Index}");
}

Or if you prefer to stick with for loops instead of Linq then all you need is a HashSet<int> to keep track of the values you've already seen.

int[] arr = { 3, 1, 2, 2, 1, 2, 3, 3 };
int k = 4;
HashSet<int> seen  = new HashSet<int>();

for(int i = 0; i < arr.Length; i++)
{
    if(!seen.Add(arr[i]))
    {
        continue;
    }

    int count = 1;
    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[i] == arr[j])
        {
            count++;
            if (count > (arr.Length / k))
            {
                Console.WriteLine(arr[i] + " " + i );
                break;
            }
        }
    }
}

Note that Add returns false when the value is already in the hash set.

于 2018-09-03T21:32:50.160 回答
0

Would this not be the most optimised way? Because you don't want to check the last arr.Length/k elements because if all were the same then they would only be are.Length/k and not > are.Length/k in Quantity

int[] arr = { 3, 1, 2, 2, 1, 2, 3, 3 };
int k = 4;
int target = arr.Length/k;
for(int i = 0; i < arr.Length - target; i++)
{
    int count = 1;
    for (int j = i + 1; j < arr.Length; j++)
   {
        if (arr[i] == arr[j])
       {
           count++;
           if (count > (target))
           {
               Console.WriteLine(arr[i] + " " + i );
               break;
           }
       }
   }
}

If you could use an algorithm to sort of O(n log n) or less then something like this may be useful:

int[] arr = { 3, 1, 2, 2, 1, 2, 3, 3 };
int[] sorted = Sort(arr); //sort method
int k = 4;
int target = arr.Length/k;
int count = 0;
for(int i = 0; i < arr.Length - target; i++)
{
     count++;
     if(arr[i] != arr[i+1])
     { 
        if(count > target)
           Console.WriteLine($"{arr[i]} {count}");
        count = 0;
     }
}
于 2018-09-03T21:57:51.223 回答