CODEWITHSUNDEEP
cc99
unclephil123
unclephil123

Reputation: 67

find the n largest elements in an array

I have an array and I need to find n tie cases in the array for example {1,2,3,3} I need the program to return both 3's 

void print_winner(void)
{
    // TODO
    string arr[9];
    string name = "";
    int largest = 0;
    for (int i = 0; i < voter_count; i++)
    {
        if (largest<candidates[i].votes)
        {
            largest = candidates[i].votes;
            name = candidates[i].name;
        }

    }

    // arr[0] = name;
    printf("%s\n", name);
    return;
}

in this code candidates is a struct with two attributes: name and votes I need the program to print the name with the highest number of votes even if there is a 3-way tie

I was thinking I would traverse the list find the largest int and then remove that int and traverse the list again to see if any elements equal the largest element from the original list and if so add the name to the array and in the end print all the name(s)

Upvotes: 1

Views: 963

Answers (3)

Joop Eggen
Joop Eggen

Reputation: 109557

Until you passed every vote count, you do not know the largest vote count. The currently largest's name would be needed to be corrected when a really larger largest is found. So do:

void print_winner_1(void)
{
    // globals: candidates: array
    //          voter_count: size of array

    int largest = 0;
    for (int i = 0; i < voter_count; i++)
    {
        if (largest < candidates[i].votes)
        {
            largest = candidates[i].votes;
        }

    }
    for (int i = 0; i < voter_count; i++)
    {
        if (largest == candidates[i].votes)
        {
            printf("%s\n", candidates[i].name);
        }

    }
}

The above could store a largest_first_i for a small speed improvement.

Collecting intermediary results in full:

void print_winner_2(void)
{
    // globals: candidates: array
    //          voter_count: size of array

    string names[9]; // Tie names.
    int name_count = 0;
    int largest = 0;
    for (int i = 0; i < voter_count; i++)
    {
        if (largest < candidates[i].votes)
        {
            name_count = 0; // Reset list of ties.
            largest = candidates[i].votes;
        }
        if (largest == candidates[i].votes)
        {
            if (name_count == 9) { // More than 9 temporary (!) ties.
                print_winner_1();
                return;
            }
            names[name_count++] = candidates[i].name;
        }

    }
    for (int i = 0; i < name_count; i++)
    {
        printf("%s\n", names[i]);
    }
}

I did one with two full loops, and one collecting the ties immediately. The second solution is prone to overflow of the result array (if there are more than 9 candidates), say in the case of [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 23] the first intermediary tie would overflow for largest == 0.

Also the second need not be faster, as you need to store into names and for every increase of largest. Almost a case of premature optimization.

Upvotes: 0

MelvinWM
MelvinWM

Reputation: 749

An approach in programming that is often good is to divide the problem up and solve its separate parts.

In this case, one way of setting up the problem is to print the names of all those that have the highest score. But that problem is somewhat complex.

An alternative way of setting up the problem would be as follow:

  • Find the maximum score.
  • After having found the maximum score, print the names of all those that have the highest score.

Each of these sub-problems are easier, and should together solve the problem.

I much prefer teaching others how to fish, so I don't want to spoil or ruin your chances for learning and improving and becoming awesome by implementing the solution for you in code. You are more than welcome to ask for clarification, however, I very much like to help :).

Upvotes: 4

Kuntal Das
Kuntal Das

Reputation: 59

I think u just need to loop the array again after you find the candidate with max votes, to look for if there is another candidate or more with same no. of votes.No need to remove records.

Upvotes: 2

Related Questions