0

This question is related to Find the first un-repeated character in a string in which input is character array and we can take hash of size 256.

But what if,

  • the elements in the array are integers of wide range, hash can be extremely costly.

  • the array contains heterogeneous elements, integers or characters, then how can hash tackle this.

we can use brute-force method of scanning entire array for each element but in worst case it takes O(n²).

Any other ideas?

Community
  • 1
  • 1
unknown_boundaries
  • 1,482
  • 3
  • 25
  • 47
  • @MatthewD may not work. It returns repeated element but may not first one. – unknown_boundaries Feb 20 '13 at 06:00
  • You'd have to make a copy of the array so you can traverse it to identify the first repeated element. But you don't want to use any 'external' arrays... – MatthewD Feb 20 '13 at 10:46
  • Refer [this](http://stackoverflow.com/questions/10767284/finding-the-first-duplicate-in-an-int-array-java/35584875#35584875) Java Implementation – craftsmannadeem Feb 23 '16 at 18:02

2 Answers2

1

A offline version: sort the vector like this:

vector<std::pair<int,int> > data;
for (int i=0;i<orignalVec.size();++i)
    data.push_back( make_pair(originalVec[i] , i ) );

Then scan through the vector, look for a pair of whose first value is the same and position value is the smallest. This gives a O(NlogN)

An online version. Use std::map (O(NlogN)) std::unordered_map(O(N)).

If the elements in the array are integers of wide range, hash can be extremely costly.

Why? Hash is designed to get around this problem isn't it?

If the array contains heterogeneous elements, integers or characters, then how can hash tackle this.

Write different hash function for each of these. For types like int, float, std::string I think STL has builtin hash.

For heterogeneous container whose element does not support comparison operation, hash is the only thing I can come up with.

phoeagon
  • 2,080
  • 17
  • 20
  • actually your solution seems to be correct as you are considering smallest positional value for the repeated elements. As i don't know about vector thing, i'm not getting it. Can you explain in terms of algorithm or psuedocode. Thanks for your suggestion. – unknown_boundaries Feb 20 '13 at 09:28
  • @PrakharBansal `std::vector` is just an array of variable length. – phoeagon Feb 20 '13 at 09:41
1

First sort the array in ascending or descending order. Then loop through the sorted array starting from second element and compare every element with the previous element to see if they are matching.

int[] numbers = {1, 5, 23, 2, 1, 6, 3, 1, 8, 12, 3};
Arrays.sort(numbers);

for (int i = 1; i < numbers.length; i++) {
    if (numbers[i - 1] == numbers[i]) {
        System.out.println("Repeated numbers are : " + numbers[i]);
    }
}
Nithin Kumar Biliya
  • 2,763
  • 3
  • 34
  • 54
Krishna
  • 11
  • 1