3

我阅读了一个工作面试问题，为以下内容编写了一些代码：

编写一个高效的函数来查找字符串中第一个不重复的字符。例如，“total”中第一个不重复的字符是“o”，“teeter”中第一个不重复的字符是“r”。讨论算法的效率。

我在 Python 中提出了这个解决方案；但是，我相信还有更漂亮的方法可以做到这一点。

word="googlethis"
dici={}

#build up dici with counts of characters
for a in word:
    try:
        if dici[a]:
            dici[a]+=1
    except:
        dici[a]=1

# build up dict singles for characters that just count 1 

singles={}
for i in dici:
    if dici[i]==1:
        singles[i]=word.index(i)

#get the minimum value

mini=min(singles.values())

#find out the character again iterating...

for zu,ui in singles.items():
    if ui==mini:
        print zu

有没有更简洁有效的答案？

4

22 回答 22

9 
In [1033]: def firstNonRep(word):
   ......:     c = collections.Counter(word)
   ......:     for char in word:
   ......:         if c[char] == 1:
   ......:             return char
   ......:         

In [1034]: word="googlethis"

In [1035]: firstNonRep(word)
Out[1035]: 'l'

编辑：如果您想在不使用帮助器的情况下实现相同的功能，例如Counter：

def firstNonRep(word):
    count = {}
    for c in word:
        if c not in count:
            count[c] = 0
        count[c] += 1
    for c in word:
        if count[c] == 1:
            return c
于 2013-01-24T21:46:06.800 回答
2 
sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]

我认为还是 DSM 的也同意

next(c for c in word if word.count(c) == 1)

这稍微更有效

>>> word = "teeter"
>>> sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]
'r'
>>> word = "teetertotter"
>>> sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]
'o'
>>> word = "teetertotterx"
>>> sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]
'o'
于 2013-01-24T21:45:29.497 回答
2 
from collections import defaultdict
word="googlethis"
dici=defaultdict(int)

#build up dici with counts of characters
for a in word:
    if dici[a]:
        dici[a]+=1
for a in word:
    if didic[a] < 2:
        return a

那不行吗？

于 2013-01-24T21:47:34.767 回答
2

更优雅的方式

def NotRepeatingCharacter(s):
    for c in s:
        if s.find(c) == s.rfind(c):
            return c
    return '_'
于 2018-03-04T19:19:00.597 回答
1

问题：字符串中的第一个非重复字符

方法一：制作计数数组

a = "GGGiniiiiGinaaaPrrrottiijayi"
count = [0]*256
for ch in a: count[ord(ch)] +=1
for ch in a :
    if( count[ord(ch)] == 1 ):
        print(ch)
        break

方法2：列表理解

# 1st  non repeating character
pal = [x for x in a if a.count(x) == 1][0]
print(pal)

方法三：字典

d={}
for ch in a: d[ch] = d.get(ch,0)+1
aa = sorted(d.items(), key = lambda ch  :ch[1])[0][0]
print(aa)
于 2018-05-08T06:51:17.837 回答
0

我的解决方案。我无法说出它的效率。我认为它在 n^2 时间内运行。

>>> def fst_nr(s):
...     collection = []
...     for i in range(len(s)):
...             if not s[i] in collection and not s[i] in s[i+1:]:
...                     return s[i]
...             else:
...                     collection+=[s[i]]
... 
>>> fst_nr("teeter")
'r'
>>> fst_nr("floccinaucinihilipilification")
'u'
>>> fst_nr("floccinacinihilipilification")
'h'
>>> fst_nr("floccinaciniilipilification")
'p'
>>> fst_nr("floccinaciniiliilification")
't'
>>> fst_nr("floccinaciniiliilificaion")
>>>

对一个不起眼的 Stack 菜鸟有什么建议吗？

于 2013-01-24T23:11:36.750 回答
0

我认为最坏的情况是 O(n^2) 但对我来说很清楚：

def firstNonRep(word):
    """the first non-repeating character in a string: "ABCA" -> B """
    for (i, c) in enumerate(word):
        residual = word[i+1:]
        if not c in residual:
            return c
于 2016-01-12T21:43:58.653 回答
0

Python; O(N+N) 我认为。

def find_first_non_occuring(test_str):
    results = {}
    for letter in test_str:
        if letter in results.keys():
            if results[letter] == 1:
                results[letter] = results[letter]+1
        else:
            results[letter] = 1 

    for letter in test_str:
        if results[letter] is 1:
            return letter
test_str = 'afixuboshafe fafd weagdgdg'
print find_first_non_occuring(test_str)
于 2016-02-09T20:40:29.483 回答
0

三行python代码即可得到解决方案：

word="googlethis"
processedList = [x for x in word if word.count(x)==1]
print("First non-repeated character is: " +processedList[0])

或者，

word="googlethis"
print([x for x in word if word.count(x)==1][0])
于 2016-12-29T20:05:39.393 回答
0

以下代码仅遍历字符串一次。这是一个简单易行的问题解决方案，但同时空间复杂性受到影响。

def firstNonRepeating(a):
    inarr = []
    outarr = []

    for i in a:
        #print i
        if not i in inarr:
            inarr.append(i)
            outarr.append(i)
        elif i in outarr:
            outarr.remove(i)
        else:
            continue
    return outarr[0]

a = firstNonRepeating(“Your String”)
print a
于 2017-01-12T17:08:13.707 回答
0 
def firstnonrecur(word):

    for c in word:
        if word.count(c) == 1:
            print(c)
            break


firstnonrecur('google')

这个怎么样？

于 2017-09-25T06:52:46.717 回答
0

由于我们需要第一个不重复的字符，最好使用集合中的 OrderedDict，因为 dict 不保证键的顺序

from collections import OrderedDict
dict_values = OrderedDict()
string = "abcdcd"

for char in string:
   if char in dict_values:
   dict_values[char] += 1
else:
    dict_values[char] = 1

for key,value in dict_values.items():
    if value == 1:
       print ("First non repeated character is %s"%key)
       break
    else:
       pass
于 2017-10-30T03:30:20.447 回答
0 
def non_repeating(given_string):
    try:
        item = [x for x in given_string[:] if given_string[:].count(x) == 1][0]
    except:
        return None
    else:
        return item

# NOTE: The following input values will be used for testing your solution.
print non_repeating("abcab") # should return 'c'
print non_repeating("abab") # should return None
print non_repeating("aabbbc") # should return 'c'
print non_repeating("aabbdbc") # should return 'd'
于 2017-11-27T11:10:08.667 回答
0

def firstNotRepeatingCharacter(s):

    对于 s 中的 c：

        如果 s.find(c) == s.rfind(c)：

            返回 c

    返回 '​​_'

于 2017-12-15T10:31:25.827 回答
0 
input_str = "interesting"
#input_str = "aabbcc"
#input_str = "aaaapaabbcccq"


def firstNonRepeating(param):
    counts = {}        
    for i in range(0, len(param)):

    # Store count and index repectively
        if param[i] in counts:
            counts[param[i]][0] += 1
        else:
            counts[param[i]] = [1, i]

    result_index = len(param) - 1
    for x in counts:
        if counts[x][0] == 1 and result_index > counts[x][1]:
            result_index = counts[x][1]
    return result_index

result_index = firstNonRepeating(input_str)
if result_index == len(input_str)-1:
    print("no such character found")
else:
    print("first non repeating charater found: " + input_str[result_index])
于 2018-08-28T16:32:20.477 回答
0 
# I came up with another solution but not efficient comment?
str1 = "awbkkzafrocfbvwcqbb"
list1 = []
count = 0
newlen = len(str1)
find = False


def myfun(count, str1, list1, newlen):

    for i in range(count, newlen):

        if i == 0:

            list1.append(str1[i])

        else:
            if str1[i] in list1:
                str1 = str1.translate({ord(str1[i]): None})
                print(str1)
                newlen = len(str1)
                count =0
                i = count
                list1.pop()
                myfun(count,str1,list1,newlen)
            else:
                pass

    if str1.find(list1[0], 1, len(str1)) != -1 :
        pass
    else:
        print(list1[0]+" is your first non repeating character")
        exit()


myfun(count, str1, list1, newlen)
于 2020-02-07T15:29:14.467 回答
0

简单的Python3解决方案

def findFirstUniqueChar(s):
    d = {}
    for c in s:
        if c in d:
            d[c] += 1
        else:
            d[c] = 1

    for c in s:
        if d[c] == 1:
            return s.index(c)
    return -1
于 2020-03-10T11:28:08.407 回答
-1

这里的想法是使用一些默认值初始化一个数组，例如 0。当您遇到字符串中的特定字符时，您只需使用您最初定义的数组中该字符的 ASCII 值来增加计数器。

在传递字符串时，您必须更新数组中字符的相应计数器。现在需要再遍历一次数组，并检查是否有任何等于 1 的值，如果有的话 - 只需将该字符作为给定字符串中的第一个非重复字符返回。

class FindFirstUniqueChar
{
    private static char ReturnFirstUniqueChar(string sampleString)
    { 
        // Initialize a sample char array and convert your string to char array.           
        char[] samplechar = sampleString.ToCharArray();

        // The default array will have all value initialized as 0 - it's an int array. 
        int[] charArray = new int[256];

        // Go through the loop and update the counter in respective value of the array 
        for (int i = 0; i < samplechar.Length; i++)
        {
          charArray[samplechar[i]] = charArray[samplechar[i]] + 1;
        }

        // One more pass - which will provide you the first non-repeated char.
        for (int i = 0; i < charArray.Length; i++)
        {

            if (charArray[samplechar[i]] == 1)
            {
                return samplechar[i];
            }
        }

        // Code should not reach here. If it returns '\0'
        // that means there was no non-repeated char in the given string. 
        return '\0';
    }

    static void Main(string[] args)
    {
        Console.WriteLine("The First Unique char in given String is: " +                         
                          ReturnFirstUniqueChar("ABCA"));
        Console.ReadLine();
    }
}

我只提供了一个示例代码。它不包括错误检查和边缘情况。对于那些有兴趣了解给定算法的时间复杂度的人 - 它是 O(N) + O(N) = O(2N)，几乎是 O(N)。它确实使用了额外的内存空间。欢迎您的反馈。

于 2014-04-08T01:37:43.787 回答
-1

在 Java 中，1) 创建字符计数哈希图。对于每个字符，如果字符中没有存储值，则将其设置为 1。否则将字符的值增加 1。

2）然后我扫描每个字符的字符串。如果 hashmap 中的计数为 1，则返回字符。如果没有字符计数为 1，则返回 null。

package com.abc.ridhi;
import java.util.HashMap;
import java.util.Scanner;

public class FirstNonRepeated {

    public static void main(String[] args) {
        System.out.println(" Please enter the input string :");
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char c = firstNonRepeatedCharacter(s);
        System.out.println("The first non repeated character is :  " + c);
    }

    public static Character firstNonRepeatedCharacter(String str) {
    HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
        int i, length;
        Character c;
        length = str.length(); 
        // Scan string and build hashmap
        for (i = 0; i < length; i++) {
            c = str.charAt(i);
            if (map1.containsKey(c)) {
                // increment count corresponding to c
                map1.put(c, map1.get(c) + 1);
            } else {
                map1.put(c, 1);
            }
        }
        // Search map in order of string str

        for (i = 0; i < length; i++) {
            c = str.charAt(i);
            if (map1.get(c) == 1){
                return c;
        }
        }
        return null;
    }
}
于 2016-08-16T05:40:15.743 回答
-1 
str = "aabcbdefgh"
lst = list(str)

for i in [(item, lst.count(item)) for item in set(lst)]:
    if i[1] == 1:
        print i[0],
于 2017-12-29T16:12:04.587 回答
-1 
enter code here

公共类 FirstRepeatingAndNonRepeatingElements {

/**
 * 
 * @param elements
 * @return
 */
private int firstRepeatedElement(int[] elements) {
    int firstRepeatedElement = -1;
    if(elements!=null && elements.length>0) {
        Set<Integer> setOfElements = new HashSet<>();
        for(int i=elements.length-1;i>=0;i--){
            if(setOfElements.contains(elements[i])) {
                firstRepeatedElement = elements[i];
            } else {
                setOfElements.add(elements[i]);
            }
        }
    }
    return firstRepeatedElement;
}


private int  firstNonRepeatedHashSet(int [] elements)  {
    int firstNonRepatedElement = -1;
    Set<Integer> hashOfElements = new HashSet<>();
    if(elements!=null && elements.length>0) {
        for(int i=elements.length-1;i>=0;i--) {
            if(!hashOfElements.contains(elements[i])) {
                hashOfElements.add(elements[i]);
                firstNonRepatedElement = elements[i];
            }
        }
    }
    return firstNonRepatedElement;
}


/**
 * @param args
 */
public static void main(String[] args) {
    FirstRepeatingAndNonRepeatingElements firstNonRepeatingElement = 
            new FirstRepeatingAndNonRepeatingElements();
    int[] input = new int[]{1,5,3,4,3,5,6,1};

    int firstRepeatedElement = firstNonRepeatingElement.
            firstRepeatedElement(input);

    System.out.println(" The First  Repating Element is "
            + firstRepeatedElement);


    int firstNonRepeatedElement = firstNonRepeatingElement.
            firstNonRepeatedHashSet(input);

    System.out.println(" The First Non Repating Element is "
            + firstNonRepeatedElement);

}
于 2018-04-08T09:27:54.147 回答
-1 
import java.util.LinkedHashMap;

public class FirstNonRepeatedCharacter {

    public static void main(String[] args) {

        String str = "sasasasafng";

        firstNonRepeatedCharacterUsingCollection(str);

    }

    private static void firstNonRepeatedCharacterUsingCollection(String str) {

        LinkedHashMap<Character, Integer> hm = new LinkedHashMap<Character, Integer>();

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

        for (Character c : hm.keySet()) {
            if (hm.get(c) == 1) {
                System.out.println(c);
                return;
            }
        }

    }
}

通过使用 LinkedHashset，我们可以获得插入顺序。

于 2021-01-10T06:07:26.600 回答