CareerCup

Quick Solution -
Try using LinkedHashMap(read java class) to preserve the order of insertion into hashtable.
e.g. 1,1,3,4,4,3,5,6,6,7
Step1 - Traverse the given array, build a LinkedHashMap. [key, value] = [array[i], count]
a. Check the key(array[i]) in hashtable, if its there increase the value(count) for that key by one. else put in hashtable with value as 1.
Step 2 - Traverse the map and keep checking count, if its 1 return the key.
I think, it can be solved without extra space. Bitwise operator may help. Thinking.....

int test2 ()
{
    int src[] = {1, 2, 3, 4, 1, 2, 3, 3, 6, 9, 0, 8, 8, 6};
    int test[ 100 ] = {0};  // size must be bigger then max element in array src

    int result = -1;

    for(int i = _countof(src)-1; i >= 0; i--)
    {
        if( !test[ src[i] ] )
        {
            result = src[i];
        }
        test[ src[i] ]++;
    }
    return result;
}

Here I have used Map from STL. In first pass, initialize the map such that unique element values will be zero and the rest of the values will be -1. In second pass for the element that has map value zero return that element.

#include <iostream>
#include <map>

using namespace std;

int firstNonDup(int arr[], int size)
{
	map<int, int> mymap;
	map<int, int>::iterator itr;
	
	for(int i=0; i<size;i++)
	{
		if(!mymap.count(arr[i]))
			mymap[arr[i]] = 0;
		else
			mymap[arr[i]] = -1;
	}
	
	for(itr = mymap.begin(); itr != mymap.end(); itr++)
		cout << "Key:  " << itr->first << "     Value:    " << itr->second << endl;
	
	for(int i=0; i<size;i++)
	{
		if(!mymap.find(arr[i])->second)
			return arr[i];
	}
	
	return 0;
}

int main()
{
	//int arr[] = {7, 97, 33, 33, 11, 11, 97};
	int arr[] =  {1,2,3,1,2,3,4,5,6,7,7,6,5};
	
	int val = firstNonDup(arr, 13);
	
	cout << "First non duplicate value is: " << val << endl;
	getchar();
	return 0;
}

Result:
	
Key:  1     Value:    -1
Key:  2     Value:    -1
Key:  3     Value:    -1
Key:  4     Value:    0
Key:  5     Value:    -1
Key:  6     Value:    -1
Key:  7     Value:    -1
First non duplicate value is: 4

What about just loading up a hashmap incrementing the count for each element on the first pass... (element, count) = ({1,2},{2,3},{10,1})... then make a second pass of the original array and the first value corresponding in the hash with count=1 is the number? performance O(2n) from 2 passes but O(n) amortized?

Maintain extra array and hashtable.

If you see an input array element A, for first time, put it on end of the extra array at say index i. Insert A into hashtable, with key as A and value as i, increment i.

If A has appeared before, lookup the index where we put it in the extra array and clear that part.

Proceed to next element in input array.

Once you are done with input array, walk the extra array and pick the first element which isn't cleared.

To maintain cleared status, you can use a Pair of integer, bool if you want.

The pseudo code will be something like this

struct ClearedInt {
    public int value;
    public bool cleared;
};
   
int firstUnique(int [] inp) {
     ClearedInt [] extra = new ClearedInt[inp.Length];
    
      HashMap <int, int> seen = new HashMap<int,int>();
    
      int currIndex = 0;
      foreach (int A in inp) {
          if (seen.Contains(A)) {
              int idx = seen[A];
              extra[idx].cleared = true;
              continue;
          }
          extra[currIndex].value = A;
          extra[currIndex].cleared = false;
          seen[A] = currIndex;
          currIndex++;
      }
   
      foreach (ClearedInt cA in extra) {
           if (!cA.cleared) return cA.value;
      }
      throw NoneUniqueException();
}

instead what i was thinking the hash map what you are calling i will call it is a key value pair or a dictionary(i am more a .Net guy).

for every element we will check if the entry is present in the dictionary or not by simple trying to retrieve the value by passing the ky, if it is present let us increment the count of the value.

at the end we can check whose count is only one and then print the output. how does that sound

static void Main(string[] args)
        {
            int[] input = {1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6,1, 12, 3, 34, 1};
            int firstNumber= input[0], secondNumber = input[0];
            var numbers = new Dictionary<int, int>();
            foreach (int t in input)
            {
                try
                {
                    if (numbers[t] == 0)
                    { }

                }
                catch (Exception)
                {
                    numbers.Add(t, 1);
                    continue;
                }
                
                numbers[t]++;
            }

            foreach (KeyValuePair<int, int> abc in numbers)
            {
                if (abc.Value == 1)
                {
                    Console.WriteLine(abc.Key);
                    break;
                }
            }

            Console.ReadLine();
        }

Use Java's BitSet API. Traverse the given array. Use each element of the array as an index into the Bit vector. While you do that, check if the bit is set or not. If not, set it, else if set, then flag it - that is your first repeating number.

int src[] = {1, 2, 3, 4, 1, 2, 3, 3, 6, 9, 0, 8, 8, 6};
std::vector<int> out;
std::vector<int>::iterator it;
for(int i = 0; i < sizeof(src) / sizeof(src[0]); ++i)
if ( (it = find(out.begin(), out.end(), src[i])) != out.end() )
out.erase(it);
else
out.push_back(src[i]);

std::cout << out.front() << std::endl;

int printFirstUnique(vector<int> a)
{
    map<int, int> nums;
    for(int i = 0; i < a.size(); i++)
        nums[a[i]]++;
    for(int i = 0; i < a.size(); i++)
        if(nums[a[i]] == 1)
            return a[i];
}

Integer findFirstUnique(int[] array){
		
		Integer firstUnique = null;
		LinkedHashSet<Integer> set = new LinkedHashSet<Integer>();
		if(array != null)
		for(int i = array.length -1; i >= 0; i--){
			if(set.add(new Integer(array[i]))){
				firstUnique = array[i];
			}
		}
		return firstUnique;
	}

use hash map.during first go set the count of integer.in second go find the no whoes count is 1.o(2n)~=o(n)

I have found out more now...



down vote



This page summarises some of the time comlplexities for various collection types with Java, though they should be exactly the same for .NET.

I've taken the tables from that page and altered/expanded them for the .NET framework. See also the MSDN pages for SortedDictionary and SortedList, which detail the time complexities required for various operations.


--------------------------------------------------------------------------------


Searching
Type of Search/Collection Types Complexity Comments
Linear search Array/ArrayList/LinkedList O(N) Unsorted data.
Binary search sorted Array/ArrayList/ O(log N) Requires sorted data.
Search Hashtable/Dictionary<T> O(1) Uses hash function.
Binary search SortedDictionary/SortedKey O(log N) Sorting is automated.

static void Main(string[] args)
        {
            int[] input = { 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 12, 3, 34, 1 };
            int firstNumber = input[0], secondNumber = input[0];
            var number2 = new HashSet<int>();

            var numbers = new Dictionary<int, int>();

            foreach (int t in input)
            {
                if (numbers.ContainsKey(t))
                {
                    numbers[t]++;
                }


                else
                {
                    numbers.Add(t, 1);
                    continue;
                }

            }

            foreach (KeyValuePair<int, int> abc in numbers)
            {
                if (abc.Value == 1)
                {
                    Console.WriteLine(abc.Key);
                    break;
                }
            }

            Console.ReadLine();
        }

take to Vectors/ArrayLists/HashTable one contain single-elements and another multipleOccuring Elements, So any element if its not there in both the Lists, then will be put in Vector1(singleelement List), any element found in one of it will be removed from singleelementList and put in MultipleOccurance. So after this.... Re-Traverse the original list any number found in the SingleList is the one

int a[10]={1,2,3,1,5,2,7,3,5,8};

int tgtIndex=0;
int count=0;

for(int i=0; i<10; i++)
{
if(a[tgtIndex] == a[i])
{
count++;
}
if(count>1)
{
tgtIndex++;
i = -1;
count=0;
}
}

cout<<"Very First Unique value in array is: "<<a[tgtIndex]<<endl;

int a[10]={1,2,3,1,5,2,7,3,5,8};

int tgtIndex=0;
int count=0;

for(int i=0; i<10; i++)
{
if(a[tgtIndex] == a[i])
{
count++;
}
if(count>1)
{
tgtIndex++;
i = -1;
count=0;
}
}

cout<<"Very First Unique value in array is: "<<a[tgtIndex]<<endl;

consider this piece of code..
Map data=new HashMap();
for(int i=0;i<arr.length;i++)
{
Integer tmp=(Integer)data.get(new Integer(arr[i]));
Integer nwtmp=(tmp==null)? new Integer(1):new Integer(tmp.intValue()+1);
data.put(new Integer(arr[i]),nwtmp);
}

Iterator itr=data.entrySet().iterator();
int res;
while(itr.hasNext())
{
Map.Entry entry=(Map.Entry) itr.next();
Integer key=(Integer)entry.getKey();
Integer count=(Integer)entry.getValue();
int cnt=count.intValue();
if(cnt ==1)
{
res=key.intValue();
break;
}
}
//res will be the output

use count sort