1

Suppose I have an unsorted integer array {3, -1, 4, 5, -3, 2, 5}, and I want to find the maximum non-repeating number (4 in this case) (5 being invalid as it is repeated). How can I achieve this?

user180940
  • 324
  • 1
  • 18
  • Sort the array (O(n log n)) and then iterate from the end of the array, taking the middle element when I see three different elements (O(n)). – user180940 Sep 19 '16 at 19:53
  • That should work as long as there are at least 3 entries in the list. Did you try it and it didn't work properly? – Always Learning Sep 19 '16 at 19:58
  • I'm pretty sure it works, at the expense of clarity (have to handle the 0,1,2 array sizes externally) but more importantly can it be done in less than O(n log n). – user180940 Sep 19 '16 at 20:00

2 Answers2

1

Use an unordered map to count the frequencies of each element. (As an optimization, keep track of largest element encountered and skip elements lower than that.) Then, scan the map to find out the largest element with frequency exactly equal to 1.

template <typename T>  // numeric T
pair<T, bool> FindMaxNonRepeating(vector<T> const& vec) {
  unordered_map<T, int> elem2freq;
  for (auto const& elem : vec) {
    elem2freq[elem] += 1;
  }

  T largest_non_repetitive = std::numeric_limits<T>::min();
  bool found = false;
  for (auto const& item : elem2freq) {
    if (item.first > largest_non_repetitive && item.second == 1) {
      largest_non_repetitive = item.first;
      found = true;
    }
  }

  return {largest_non_repetitive, found};
}

This runs in time complexity O(n) and requires space complexity O(n).

Arun
  • 19,750
  • 10
  • 51
  • 60
  • 1
    Ah damn you Arun, I thought something like that while having lunch! Of course, this would need more space, as you mentioned, +1. – gsamaras Sep 19 '16 at 21:31
0
  1. Sort the array in descending order.
  2. Begin from top element and store it a variable, say max.
  3. Check next element with max, if they are the same, repeat until you find the next max, otherwise, you found the max non-repeated number.

Time complexity: O(nlogn)

implementation, based on my Sort (C++):

#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cstddef>

using namespace std;

void printVector(vector<int>& v)
{
    for(vector<int>::iterator it = v.begin() ; it != v.end() ; it++)
        cout << *it << ' ';
    cout << endl;
}

bool compar(const int& a, const int& b)
{
    return (a > b) ? true : false;
}


int main()
{
    vector<int> v = {3, -1, 4, 5, -3, 2, 5};
    cout << "Before sorting : " << endl;
    printVector(v);

    sort(v.begin(), v.end(), compar);

    cout << endl << "After sorting : " << endl;
    printVector(v);


    int max_non_repeat = numeric_limits<int>::min();
    for(unsigned int i = 0; i < v.size(); ++i)
    {
        if(max_non_repeat == v[i])
            max_non_repeat = numeric_limits<int>::min();
        else if(v[i] > max_non_repeat)
            max_non_repeat = v[i];
    }

    cout << "Max non-repeated element: " << max_non_repeat << endl;

    return 0;
}

Output:

C02QT2UBFVH6-lm:~ gsamaras$ g++ -Wall -std=c++0x  main.cpp 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
Before sorting : 
3 -1 4 5 -3 2 5 

After sorting : 
5 5 4 3 2 -1 -3 
Max non-repeated element: 4

For maximum pleasure, do base your (a different) approach on How to find max. and min. in array using minimum comparisons? and modify it accordingly.

Community
  • 1
  • 1
gsamaras
  • 71,951
  • 46
  • 188
  • 305