write a function that returns the first unique element in an array

Question

Xiao · Accepted Answer

What the type of elements in the array? If character, set up the hash table, and scan the array. the hash table stores the index of each element. If the element appears more than once, update the table as a negetive value. After scanning, find the smallest index value from the hash table, which would be the first uniqure element. The time complex gonna be O(n), where n is the length of array.

Xiao · Answer

I wrote a sample program here. (I use map container here to replace hash_map. The  doesnot work on my computer)

#include "stdafx.h"
#include 
#include 

using namespace std;

static int find_unique_ele(char*,int);

int _tmain(int argc, _TCHAR* argv[])
{
	char test[6] = {'a','b','c','b','c','a'};
	int min_index = find_unique_ele(test,6);
	if (min_index  store_table_value;
	map store_table;
	while(i ::const_iterator test_it = store_table.find(*test);
		if(test_it != store_table.end()){
			store_table[*test] = -1;
		}
		else{
			store_table.insert(map::value_type(store_table_value(*test,i)));
		}
		i++;
		test++;
	}

	map::const_iterator table_it = store_table.begin();
	store_table_value temp_value = *table_it;
	int min_index = temp_value.second;
	while(++table_it != store_table.end()){
		temp_value = *table_it; 
		if(temp_value.second < min_index || min_index < 0){
			min_index = temp_value.second;
		}
	}

	return min_index;
}

Sid Ray · Answer

I think in the above solution you have to scan the original array twice making it order (2n) or O(n). The 2nd scan is needed to determine the corresponding entry in the hash table whether it is unique or not. We need this to determine the first unique element in the array.

Anónimo · Answer

Sort the list then scan the list looking for a data item that does not match the previous item or the next item.

Bloomberg

Pregunta de entrevista de Bloomberg

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo