使用链表查找给定字符串中的第一个非重复字符

原文：https://www.geeksforgeeks.org/find-first-non-repeating-character-in-a-given-string-using-linked-list/

给定长度为L的字符串str，任务是查找字符串中第一个非重复字符。

示例：

输入：str = "geeksforgeeks"

输出：f

输入：str = "programmer"

输出：p

注意：请参考本文的HashMap方法，本文作为空间优化的方法。

链表方法：想法是使用链表来跟踪字符串中的唯一元素。 下面是该方法的说明：

  • 为字符串中的每个字符遍历字符串，并根据以下条件在链表中添加该字符：

    • 如果链表中已经存在该字符，则从链表中删除现有的字符节点。

    • 否则，将字符添加到链表中。

  • 最后，链表的第一个节点处的字符是字符串的第一个非重复字符。

下面是上述方法的实现：

Java

// Java implementation to find the  
// first non-repeating element  
// of the string using Linked List  

import java.util.LinkedList;  

public class FirstNonRepeatingElement {  

    // Function to find the first  
    // non-repeating element of the  
    // given string using Linked List  
    static void firstNonRepElement(String str)  
    {  
        LinkedList<Character> list  
            = new LinkedList<Character>();  

        list.add(str.charAt(0));  

        for (int i = 1; i < str.length(); i++) {  
            if (list.contains(str.charAt(i)))  
                list.remove(list.indexOf(  
                    str.charAt(i)));  
            else
                list.add(str.charAt(i));  
        }  
        System.out.println(list.get(0));  
    }  

    // Driver Code  
    public static void main(String[] args)  
    {  
        String str = "geeksforgeeks";  

        // Function Call  
        firstNonRepElement(str);  
    }  
}

C

// C# implementation to find the 
// first non-repeating element 
// of the string using Linked List 
using System;  
using System.Collections;  
using System.Collections.Generic; 

class FirstNonRepeatingElement{ 

// Function to find the first 
// non-repeating element of the 
// given string using Linked List 
static void firstNonRepElement(string str) 
{ 
    LinkedList<char> list = new LinkedList<char>(); 

    list.AddLast(str[0]); 

    for(int i = 1; i < str.Length; i++)  
    { 
        if (list.Contains(str[i])) 
            list.Remove(str[i]); 
        else
            list.AddLast(str[i]); 
    } 
    Console.Write(list.First.Value); 
} 

// Driver Code 
public static void Main(string[] args) 
{ 
    string str = "geeksforgeeks"; 

    // Function call 
    firstNonRepElement(str); 
} 
} 

// This code is contributed by rutvik_56

输出：

f

效率分析：

  • 时间复杂度：O(N * 26)

  • 辅助空间：O(n)

如果您喜欢 GeeksforGeeks 并希望做出贡献，则还可以使用 tribution.geeksforgeeks.org 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。 查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。

如果您发现任何不正确的地方，请单击下面的“改进文章”按钮，以改进本文。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://www.moonapi.com/news/33548.html