首页 > 试题广场 > 首个重复字符
[编程题]首个重复字符

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

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

测试样例:
"qywyer23tdd",11
返回:y
推荐
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)
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)

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)
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)
看到答案都是一波hash,强答一个使用位运算的解法
看过Linux-select的应该都知道,select采用fdset来记录活动描述符,他的原理是:
每一个bit表示打开的描述符,每次碰到一个活动描述符,就把它对应的位置1,例如对8进行置位:
0000000010000000
类似的,对于这道题也可以这么做。题目说是字符,也就是0~255范围,只需要用到256个bit,8个int足以!
初始化:int cset[8] = {0};
扫描string,对于每一个字符A[i],对应的位置为第row = A[i]/32 个int的第col = A[i]%32位bit。
1. 判断c重复方法如下:
( (1<<col) & cset[row] ) ! = 0当且仅当A[i ]重复
2. 置位方法如下:
cset[row] |= (1<<col);

代码如下:
class FirstRepeat {
public:
    char findFirstRepeat(string A, int n) {
        int cset[8] = {0};	//32 * 8
        for (int i = 0;i < n; ++i)
        {
            int row = A[i] / 32, col = A[i] % 32;
            if (((1<<col) & cset[row]) != 0) return A[i];
            else cset[row] |= (1<<col);	//turn-on bit
        }
        return '\0';	//not exists
    }
};

编辑于 2017-04-16 15:40:28 回复(1)
三种方法(都是基于哈希思想)
① 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)

用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)
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)
点开动态规划练习,结果除了二分和这些无脑循环,别的都不会。。道理我都懂的啊!
 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)
#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++不支持数组整体赋值,可以在声明数组时整体初始化。
无论数组有多大,全部初始化为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)
	//使用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)
利用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)
用的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)
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)
     public char findFirstRepeat(String A, int n) {
        int[] str = new int[256];
        if (n == 0 || A == null){
            return 0;
        }
        for (int i = 0; i < n; i++){
            if (str[A.charAt(i)] == 1){
                return A.charAt(i);
            }else {
                str[A.charAt(i)]++;
            }
        }
        return 0;
    } 

发表于 2017-09-30 20:43:29 回复(0)
import java.util.*;
public class FirstRepeat {
    public char findFirstRepeat(String A, int n) {
         char[] c=A.toCharArray();
         List<Character> l=new ArrayList<Character>();
    for(int i=0;i<n;i++){
     for(int j=0;j<i;j++){
      if(c[i]==c[j]){
      l.add(c[i]);
      break;
      }
      else continue;
     }
    }
        return l.get(0);
}
}

发表于 2017-09-07 16:48:18 回复(0)