CareerCup

using a hash table
scan from left to right, if the table doesn't contain current element, put it in; if it does, just return

-----------------------------------------
Sorry I took the question as "find the first duplicated char".....

as what @Saam had said, using a linkedhashMap will reduce the search time of second round


In fact, I think @Saam 's answer is good enough, but if we want to scan once, we can do this. The solution below is really trivial, while we cost much more space.

while we still have the table[256](or hashMap) to count each char's occurrence frequency, We create a linked list T, each node contains the char that is unique, while use a hashtable<char,Node> to translate the value to the node in T instantly.

Then we need only one round, check if the current char never appeared( table[current] == 0 ), add a node to T, and put it into the hashtable, then table[current]++;

if tab[current] > 0, find if the node contains the element exists using the hashtable, remove the node from T.

Then the first element of T would be the answer when first round ends.

#include<stdio.h>
#include<string.h>
int num[26]={0};
int index[26]={0};
int main()
{
char *s="abbbccdefafgg ";
int i;
for(i=0;i<strlen(s);i++)
{
num[s[i]-'a']++;
index[s[i]-'a']=i;
}
int min=strlen(s),p=0;
for(i=0;i<26;i++)
if(num[i]==1 && index[i]<min)
{
min=index[i];
p=i;
}
printf("%c/n",p+'a');
return 0;
}

sort the array
Check if the first element which is not repeated.

Here is my answer to this question (put it in a link for syntax highlight):

basicalgos.blogspot.com/2012/03/22-find-first-unique-character-in-array.html

Here is my answer to this question (put it in a link for syntax highlight):

basicalgos.blogspot.com/2012/03/22-find-first-unique-character-in-array.html

make a hashmap of given array... as character ,numOfOccurence.
Now traverse array.. and the first element whose count is 1 is the first unique character

make a hashmap of given array... as character ,numOfOccurence.
Now traverse array.. and the first element whose count is 1 is the first unique character

A hastable linked to min heap.
Build a hashtable with count of each character in the array.
Build a min heap starting with the 1st character as root, whenever the root character's hastable entry count is greater than one remove the root and adjust the min heap.
At the end of string iteration the root has the 1st unique character in the array.

char Find(char* arr,int size)
{
int check[256]={0};
int i;
for (i=0; i<size; i++) {
check[arr[i]]++;
}
i=0;
while (check[i]!=1) {
i++;
}
return i;
}

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

public class FirstUniqueArrayCharacter {
	public static void main(String[] args) {
		// Test some strings
		test("aa");
		test("ab");
		test("aab");
		test("ababcbad");
	}

	private static void test(String text) {
		char[] array = text.toCharArray();

		Character c = findFirstUniqueCharacter(array);
		System.out.println("First unique character in '" + text + "' is: '" + c + "'");
	}

	// Time complexity is O(n), space complexity is O(n)
	private static Character findFirstUniqueCharacter(char[] array) {
		// Linked hash map stores entries in insertion-order by default
		Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
		for (char c : array) {
			Integer count = map.get(c);
			if (count == null) {
				count = 0;
			}
			count++;

			map.put(c, count);
		}

		for (Entry<Character, Integer> entry : map.entrySet()) {
			boolean unique = entry.getValue() == 1;
			if (unique) {
				return entry.getKey();
			}
		}

		return null;
	}

}

Assume we are only considering lower-case letters.
Complexity: O(n) time; O(1) space

public static char findUniqueChar(String s) {
    int tl = 26;
    int[] occurrence = new int[tl];
    int[] firstIdx = new int[tl];
    for (int i = 0; i < tl; i++) {
      occurrence[i] = 0;
      firstIdx[i] = -1;
    }
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      int idx = c - 'a';
      occurrence[idx]++;
      if (firstIdx[idx] == -1) {
        firstIdx[idx] = i;
      }
    }
    int smallestIdx = Integer.MAX_VALUE;
    char uniqueChar = 0;
    for (int i = 0; i < tl; i++) {
      if (occurrence[i] == 1) {
        if (firstIdx[i] < smallestIdx) {
          smallestIdx = firstIdx[i];
          uniqueChar = (char)(i + 'a');
        }
      }
    }
    return uniqueChar;
  }