首页 > 试题广场 >

首个重复字符

[编程题]首个重复字符

热度指数：42450 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一个字符串，请设计一个高效算法，找到第一次重复出现的字符。

给定一个字符串(不一定全为字母)A及它的长度n。请返回第一个重复出现的字符。保证字符串中有重复字符，字符串的长度小于等于500。

测试样例：

"qywyer23tdd",11

返回：y

算法知识视频讲解

推荐

webary


	classFirstRepeat {



	public:



	    charfindFirstRepeat(string A, intn) {



	        bool times[256] = {0};



	        if(A.size()==0|| n==0)



	            return0;



	        for(inti=0;i<n;i++) {



	            if(!times[A[i]])



	                times[A[i]] = 1;



	            else



	                returnA[i];



	        }



	    }



	};

利用hash的方式，把每个字符是否出现记录到一个数组中，初始化时都没出现，遍历字符串，将对应字符的位置置1，表示出现了，如果在某个字符位置上已经为1了，表示前面出现过该字符，那么这个字符就是第一个重复出现的字符，返回即可

编辑于 2015-11-26 00:48:53 回复(28)

C/C++

XD小牛

class FirstRepeat {
public:
    char findFirstRepeat(string A, int n) {
        // write code here
        bool times[256] ={0};
        if(A.size() == 0 || n ==0)
            return 0;
        int i;
        for( i = 0 ;i<n;i++)
        {
            if(!times[A[i]])
                times[A[i]] = 1;
            else 
                break; 
        }
       	return A[i];
    }
};

发表于 2016-07-06 11:21:10 回复(3)

冷色探戈

三种方法（都是基于哈希思想）
① HashMap
② HashSet
③ 数组Hash

package nowcoder.codingPro;

import java.util.HashMap;
import java.util.HashSet;

public class 去哪儿_首个重复字符 {

	/**
	 * 
	 * 
	 * HashMap解
	 * 
	 * @param A
	 * @param n
	 * @return
	 */
	public char findFirstRepeat_1(String A, int n) {

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

		char[] charArray = A.toCharArray();

		for (int i = 0; i < charArray.length; i++) {

			if (hm.get(charArray[i]) == null) {
				hm.put(charArray[i], 1);
			} else {
				return charArray[i];
			}
		}

		return '\n';
	}

	/**
	 * 
	 * HashSet解
	 * 
	 * @param A
	 * @param n
	 * @return
	 */
	public char findFirstRepeat_2(String A, int n) {

		HashSet<Character> hm = new HashSet<Character>();

		char[] charArray = A.toCharArray();

		for (int i = 0; i < charArray.length; i++) {

			if (hm.add(charArray[i])) {
			} else {
				return charArray[i];
			}
		}
		return '\n';
	}

	/**
	 * 
	 * 数组模拟hash 高效解法
	 * 
	 * @param A
	 * @param n
	 * @return
	 */
    public char findFirstRepeat_3(String A, int n) {
    	
    	char[] charArray = A.toCharArray();
    	int[] hashChar = new int[256]; // ASCII 范围
    	
    	for (int i=0; i<charArray.length; i++) {
    		if (hashChar[charArray[i] - '0'] == 0) {
    			hashChar[charArray[i] - '0'] = 1;
    		} else {
    			return charArray[i];
    		}
    	}
    	return '\n';
    }
}

发表于 2017-03-28 16:55:32 回复(1)

@163.com

  publicclassFirstRepeat { 

      publiccharfindFirstRepeat(String A, intn) { 

          HashSet hs=newHashSet(); 

          intlength=A.length(); 

          char[] a=A.toCharArray(); 

          for(inti=0;i<length;i++) 

              { 

              booleanb=hs.add(a[i]);//通过往hashset塞值（hashset不准有重复元素），判断当前一段数据中是否有重复元素，一但有，立刻返回 

                  if(b==false) 

                  { 

  returna[i]; 

              } 

          } 

          return'0'; 

          // write code here 

      } 

  }

发表于 2015-09-14 23:03:00 回复(4)

ahu_coder

import java.util.*;

public class FirstRepeat {
    public char findFirstRepeat(String A, int n) {
        HashSet<Character> set = new HashSet<>();
        char[] ch = A.toCharArray();
        for(char c : ch) {
            if(!set.contains(c)) {
                set.add(c);
            } else {
                return c;
            }
        }
        return '\0';
    }
}

发表于 2017-08-22 01:27:15 回复(1)

C/C++

卷积神经网络哦

用ASCII码哈希O(n)的复杂度

int arr[256];
memset(arr, 0, sizeof(arr));
for(int i=0;i<n;i++){
    arr[(int) A[i]] += 1;
    if(arr[(int)A[i]] > 1)
        return A[i];
    return 'a';
}

编辑于 2018-08-22 22:04:26 回复(1)

Python

华科平凡

python解法

def findFirstRepeat(self, A, n):
        chars=[]
        for i in A:
            if i not in chars:
                chars.append(i)
            else:
                return i

编辑于 2017-09-12 10:35:29 回复(2)

Java

咖啡新东方

点开动态规划练习，结果除了二分和这些无脑循环，别的都不会。。道理我都懂的啊！

public char findFirstRepeat(String A, int n) {
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(A.charAt(i)==A.charAt(j)) return A.charAt(i);
}
}
return '!';
}

发表于 2018-02-27 23:13:13 回复(1)

C/C++

Cavs

#include<unordered_set>
class FirstRepeat {
public:
    char findFirstRepeat(string A, int n)
    {
        unordered_set<char> hs;
        for(auto& c:A) 
        {
            if(hs.find(c) != hs.end()) return c;
            hs.emplace(c);
        }
        
        return ' ';
    }
};

发表于 2017-08-15 16:32:28 回复(0)

C/C++

cycleof

/*C/C++不支持数组整体赋值，可以在声明数组时整体初始化。
无论数组有多大，全部初始化为0的操作很简单，如int a[3000]={0};就可以将a的3000个元素全部置0；
若要赋其他值，例如全部赋值为7，写成int a[3000]={7};则不行，这只给a[0]赋值为7，其余的都是0。*/
class FirstRepeat {
public:
    char findFirstRepeat(string A, int n) {
        int a[256] = {0};
        int i;
        if( n==0 || A.size() == 0 ){
            return 0;
        }
        else{
            for(i=0;i<n;i++){
                if( !a[ A[i] ] )
                    a[ A[i] ] = 1;
                else
                    break;
            }
        }
        return A[i];
    }
};
//遍历原数组，新建数组存储不重复元素
class FirstRepeat {
public:
    char findFirstRepeat(string A, int n) {
        char a[500];
        int i,j,x=0,z=0;
        for(i=0;i<n;i++){
            for(j=0;j<x;j++){
                if(a[j] == A[i]){
                    z = 1;
                    break;
                }
            }
            if(z == 1)
                break;
            if(j == x)
                a[x++] = A[i];
        }
        return A[i];
    }
};

编辑于 2017-07-10 18:43:44 回复(0)

qibofang

	//使用set，依次压入元素，来判断第一个在set中出现的字符，符合题意
    char findFirstRepeat(string A, int n) {
        // write code here
		set<char> chset;
		int i;
		for(i=0; i<n; ++i){
			if(chset.find(A[i]) == chset.end())
				chset.insert(A[i]);
			else
				break;
		}
		return A[i];
    }
	//第一次没看清题意，返回的是字符串中最前面的重复字符，如abba，返回了a，不合题意
    char findFirstRepeat(string A, int n) {
        // write code here
        int i;
        string::size_type idx = 0;
        for(i=0; i<n-1; ++i){
            string tmp = A.substr(i, 1);
            if((idx = A.find_first_of(tmp, i+1)) != string::npos)
                break;
        }
        return A[idx];
    }

发表于 2016-09-08 19:34:28 回复(0)

Java

曙光女神

利用list存储不相同的字符，当第一个重复的字符进入list，则返回此字符。

count则是判断list的大小，字符不重复，那么count就等于list长度；否则即为第一个重复的字符。

    importjava.util.*;  

    publicclassFirstRepeat {  

        publiccharfindFirstRepeat(String A, intn) {  

            // write code here  

           charc=0;  

            List<Character> list
    = newArrayList<Character>();  

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

            for(inti = 1; i < n;i++)  

            {  

                intcount =0;  

               for(intj = 0; j < list.size() ; j++)  

               {  

                   if(A.charAt(i) != list.get(j)) count++;  

               }  

                if(count == list.size())  

                {  

                    list.add(A.charAt(i));  

                }  

                else  

                {  

                    c = A.charAt(i);break;  

                }  

            }  

            returnc;  

        }  

    }

发表于 2016-09-03 13:39:48 回复(0)

叫我加班狂

#include <iostream>
using namespace std ;

class FirstRepeat{
public:
	char find_first_repeat(char *s,int n){
		int hash[500] = {0} ;
		if(s == NULL || n == 0){
			return 0;
		}
		int i ;
		for(i=0;i<n;i++){
			if(hash[s[i]] != 0){
				return s[i];
			}else{
				hash[s[i]] = 1 ;
			}
		}
		return s[i] ;
	}

};

int main(){
	FirstRepeat *firstrepeat = new FirstRepeat() ;
	char *s = "qywyer23tdd" ;
	char c = firstrepeat->find_first_repeat(s,11) ;
	cout<<c<<endl ;
	return 0 ;
}

发表于 2015-09-16 16:55:49 回复(1)

pein531

用一个set记录已经出现过的字符，如果遍历到字符串中某个字符时发现它已经在set中，就直接返回它。

# -*- coding:utf-8 -*-

class FirstRepeat:
    def findFirstRepeat(self, A, n):
        # write code here
        mem = set()
        for c in A:
            if c in mem:
                return c
            mem.add(c)

发表于 2021-04-10 21:23:03 回复(0)

你快乐吗

直接循环，调用系统的方法比较方便

import java.util.*;
public class FirstRepeat {
    public char findFirstRepeat(String A, int n) {
        for (int i = 1; i < A.length(); i++) {
			if(A.substring(0, i).contains(A.subSequence(i, i+1))) 
				return A.charAt(i);
		}
        // 这里为了语法不报错，没什么意义
		return '1';
    }
}

发表于 2020-09-06 15:39:11 回复(0)

HKpeng

/*解题思路：利用hash的方式，遍历字符串，若该字符出现
一次就在falg的对应位置上+1，若某个字符位置上的值大于1， 则表示前面出现过该字符，那么这个字符就是第一个重复出现的字符，
直接返回该字符*/
char findFirstRepeat(string A, int n)
{
    int flag[128] = {0};
    for(int i = 0; i < n; i++)
    {
        flag[A[i]]++;
        if(flag[A[i]] > 1)
            returnA[i];
    }
}

编辑于 2020-03-27 20:55:48 回复(0)

Greatiga

用的C++map函数，将字符作为键值key，插入的value随便一点插个1就行或者自己定义类型都可以，map函数作为容器，在键值不同时才可以插入数据，所以当重复键值（这里话的就是字符）出现时就会插入失败，此时返回这个字符就行。这是我的想法，欢迎大家提出建议。

char Findfirstrepeat(string A,int n)
{
    map <char,int>has;
    pair<map<char,int>::iterator,bool> Insert;
    char c;
    for(int i=0;i<n;i++)
    {
        c=A[i];
        Insert=has.insert(pair<char,int>(c,1));
        if(Insert.second==0)return c;
    }
}

发表于 2019-08-10 22:20:04 回复(0)

霍一博

class FirstRepeat {
public:
char findFirstRepeat(string A, int n) {
string q="";
for(int i=1;i<n;++i){
q=A.substr(0,i);
for(int j=0;j<q.length();++j){
if(A[i]==q[j])
return A[i];
}

// write code here
}
};

发表于 2019-07-17 11:02:37 回复(0)

搬砖炫富

//数组记录出现的次数；
import java.util.*;
public class FirstRepeat {
    public char findFirstRepeat(String A, int n) {
        int [] str = new int[128];
        for(int i=0;i<n;i++){
            if(str[A.charAt(i)]==1){
                return A.charAt(i);
            }
            str[A.charAt(i)]++;
        }
        return '0';
    }
}

编辑于 2018-07-17 18:58:27 回复(1)

认真做毕设的男孩子

class FirstRepeat {
public:
    char findFirstRepeat(string A, int n) {
        // write code here
        set<char> note;
        char result;
        for(int i=0;i<n;i++)
        {
            if(note.find(A[i])!=note.end())
            {
                result=A[i];
                break;
            }
            else
                note.insert(A[i]);
        }
        return result;
    }
};

发表于 2018-02-07 10:44:39 回复(0)

C/C++

nbgao

class FirstRepeat {
public:
    char findFirstRepeat(string A, int n) {
        bool count[256];
        memset(count,false,sizeof(count));
        if(A.size()==0 || n==0) 
            return 0;
        int k;
        for(k=0;k<n;k++)
        {
            if(!count[A[k]])
                count[A[k]] = 1;
            else
                break;         }         return A[k];
    }
};

发表于 2017-11-05 01:36:16 回复(0)