Найти первый неповторенный символ в строке

Question

Какой самый быстрый способ найти первый символ, который появляется в строке только один раз?

Answer 1

вход = выход aabbcddeef = c

char FindUniqueChar(char *a)
{
    int i=0;
    bool repeat=false;
    while(a[i] != '\0')
    {
      if (a[i] == a[i+1])
      {
        repeat = true;
      }
      else
      {
            if(!repeat)
            {
            cout<<a[i];
            return a[i];
            }
        repeat=false;
      }
      i++;
    }
    return a[i];
}

Answer 2

Another answer(Might not be so efficient but a kind of approach that we can try in c++; Time complexity:O(n) Space complexity:O(n)).

char FirstNotRepeatingCharInString(char *str)
{
    //Lets assume a set  to insert chars of string
    char result;
    multiset<char> st;
    for(int i=0;i<strlen(str);i++)
    {
        st.insert(str[i]);  
    }
    for(int i=0;i<strlen(str);i++)
    {
        if(st.count(str[i]) <=1){
            result = str[i];
            break;
        }
    }
    return result;
}

Answer 3

Следующий код на C # со сложностью n.

using System;
using System.Linq;
using System.Text;

namespace SomethingDigital
{
    class FirstNonRepeatingChar
    {
        public static void Main()
        {
            String input = "geeksforgeeksandgeeksquizfor";
            char[] str = input.ToCharArray();

            bool[] b = new bool[256];
            String unique1 = "";
            String unique2 = "";

            foreach (char ch in str)
            {
                if (!unique1.Contains(ch))
                {
                    unique1 = unique1 + ch;
                    unique2 = unique2 + ch;
                }
                else
                {
                    unique2 = unique2.Replace(ch.ToString(), "");
                }
            }
            if (unique2 != "")
            {
                Console.WriteLine(unique2[0].ToString());
                Console.ReadLine();
            }
            else
            {
                Console.WriteLine("No non repeated string");
                Console.ReadLine();
            }
        }
    }
}

Answer 4

Если массив char содержит повторяющиеся символы непрерывно (например, "ggddaaccceefgg), то будет работать следующий код:

char FirstNonRepeatingChar(char* str)
{
     int i=0;
     bool repeat = false;
     while(str[i]!='\0')
     {
       if(str[i] != str[i+1])
       {
         if(!repeat)
           return(str[i]);
         repeat = false;
       }
       else
        repeat = true;
      i++;
    }
return ' ';
}

Answer 5

Вот еще один подход ... у нас может быть массив, в котором будут храниться счетчик и индекс первого вхождения символа.После заполнения массива мы могли бы пройти через массив и найти МИНИМАЛЬНЫЙ индекс, счетчик которого равен 1, а затем вернуть str [index]

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <climits>
using namespace std;

#define No_of_chars 256

//store the count and the index where the char first appear
typedef struct countarray
{
    int count;
    int index;
}countarray;

//returns the count array
    countarray *getcountarray(char *str)
    {
        countarray *count;
        count=new countarray[No_of_chars];
        for(int i=0;i<No_of_chars;i++)
        {
            count[i].count=0;
            count[i].index=-1;
        }
        for(int i=0;*(str+i);i++)
        {
            (count[*(str+i)].count)++;
            if(count[*(str+i)].count==1) //if count==1 then update the index
                count[*(str+i)].index=i; 

        }
        return count;
    }

    char firstnonrepeatingchar(char *str)
    {
        countarray *array;
        array = getcountarray(str);
        int result = INT_MAX;
        for(int i=0;i<No_of_chars;i++)
        {
            if(array[i].count==1 && result > array[i].index)
                result = array[i].index;
        }
        delete[] (array);
        return (str[result]);
    }

    int main()
    {
        char str[] = "geeksforgeeks";
        cout<<"First non repeating character is "<<firstnonrepeatingchar(str)<<endl;        
        return 0;
    }

Answer 6

как насчет использования дерева суффиксов для этого случая ... первый неповторенный символ будет первым символом строки с самым длинным суффиксом с наименьшей глубиной в дереве ..

Answer 7

Функция:

Эта функция c # использует HashTable (словарь) и имеет наихудший регистр производительности O (2n).

private static string FirstNoRepeatingCharacter(string aword)
    {
        Dictionary<string, int> dic = new Dictionary<string, int>();            

        for (int i = 0; i < aword.Length; i++)
        {
            if (!dic.ContainsKey(aword.Substring(i, 1)))
                dic.Add(aword.Substring(i, 1), 1);
            else
                dic[aword.Substring(i, 1)]++;
        }

        foreach (var item in dic)
        {
            if (item.Value == 1) return item.Key;
        }
        return string.Empty;
    }

Пример:

string aword = "TEETER";

еЫп (FirstNoRepeatingCharacter (aword)); // печать: R

Answer 8

In Mathematica можно написать так:

string = "conservationist deliberately treasures analytical";

Cases[Gather @ Characters @ string, {_}, 1, 1][[1]]

{"v"}

Answer 9

  /**
   ** Implemented using linkedHashMap with key as character and value as Integer.
   *
   *  Used linkedHashMap to get the wordcount. 
   *  This will return a map with wordcount in the same order as in the string.
   *  
   *  Using the iterator get the first key which has value as 1.
   *  
   */

package com.simple.quesions;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class FirstNonRepeatingChar 
{
    public static void main(String args[])
    {
        String a = "theskyisblue";
        System.out.println(findNonRepeating(a));
    }

    // Function which returns the first non repeating character.

    public static char findNonRepeating(String str)
    {
       // Create a linked hash map 

        LinkedHashMap<Character,Integer> map = new LinkedHashMap();
        if(str == null)
            return ' ';
        else
        {

        // function to get the word count 

            for(int i=0;i<str.length();i++)
            {
                char val = str.charAt(i);
                if(val != ' ')
                {
                    if(map.containsKey(val))
                    {
                        map.put(val,map.get(val)+1);
                }
                else
                {
                    map.put(val, 1);
                }
            }
        }

        System.out.println(map);
    }

    // get all the keys in the set and use it in iterator.
    Set keys = map.keySet();
    Iterator itr = keys.iterator();
    char key;
    int val;

    // get the first key which has value as " 1 " .

    while(itr.hasNext())
    {
         key = (Character) itr.next();
         val = (Integer) map.get(key);
         if(val == 1)
             return key;
    }

    return ' ';
}

}

Answer 10

в С, это почти Алгоритм художника Шлемеля (не совсем O (n!), Но больше 0 (n2)).

Но превзойдет "лучшие" алгоритмыСтроки разумного размера, потому что O такой маленький.Это также может легко сказать вам местоположение первой неповторяющейся строки.

char FirstNonRepeatedChar(char * psz)
{
   for (int ii = 0; psz[ii] != 0; ++ii)
   {
      for (int jj = ii+1; ; ++jj)
      {
         // if we hit the end of string, then we found a non-repeat character.
         //
         if (psz[jj] == 0)
            return psz[ii]; // this character doesn't repeat

         // if we found a repeat character, we can stop looking.
         //
         if (psz[ii] == psz[jj])
            break; 
      }
   }

   return 0; // there were no non-repeating characters.
}

edit: этот код предполагает, что вы не имеете в виду последовательных повторяющихся символов.