首页 > 试题广场 >

首个重复字符

[编程题]首个重复字符

热度指数：42467 时间限制：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)

Java

konfupanda

import java.util.*;

public class FirstRepeat {
    public char findFirstRepeat(String A, int n) {
        // write code here
        char c=0;
        char[] cc = new char[n];
        for (int i = 0; i < A.length(); i++) {
            if(A.charAt(i)!=32){
                cc[i]=A.charAt(i);
            }
        }

        for (int i = 0; i <cc.length ; i++) {
            int m=A.split(String.valueOf(cc[i])).length;
            if(m>2){
                c=cc[i];
                break;
            }
        }
        return c;
    }
}

String类和数组都没有.lenght方法，好像有.size()错误的方法，编译环境是错的，用例也是错的

发表于 2020-05-07 13:12:40 回复(0)

Java

肥咩咪

字符统计用map集合

import java.util.*;

public class FirstRepeat 
{
    public char findFirstRepeat(String A, int n) 
    {
        char result='A';
        LinkedHashMap<String,Integer> map=new LinkedHashMap<>();
        for(int i=0;i<n;i++)
        {
            String s=""+A.charAt(i);
            if(map.get(s)!=null)//map集合中已经有该字符
            {
                result=s.charAt(0);
                return result;
            }
            else//map集合中没有该字符
            {
                map.put(s,1);
            }
        }

        return result;

    }
}

发表于 2020-03-26 23:23:35 回复(0)

Java

钱多事少离家近

int position = -1;
for (int i = 0; i < n; i++) {
char c=A.charAt(i);
if ((A.indexOf(c, i + 1)) != -1) {
position = i;
break;
}
}
char result=A.charAt(position);

return result;

这种方法在eclipse上可以通过，不知道为什么在这里不行

发表于 2019-03-19 22:47:28 回复(0)

Java

no_and_life

不会其他，使用最简单的

import java.util.*;

public class FirstRepeat {
    public char findFirstRepeat(String A, int n) {
        int arr[] =new int[n];
        for(int i=0;i<n;i++) { 
            arr[i]=n;
            for(int j=i+1;j<n;j++) {
                if(A.charAt(i)==A.charAt(j)) {
                    arr[i]=j;
                    break;
                }
            }
        }
        int flag=0;
        for(int i=1;i<n-2;i++) {
            if(arr[i]<arr[flag]) {
                flag=i;
            }
        }
        return A.charAt(flag);
    }
}

发表于 2018-04-05 13:04:29 回复(0)

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)

Java

@该昵称已被注册

import java.util.*;

public class FirstRepeat {
public char findFirstRepeat(String A, int n) {
char[] chs = A.toCharArray();
HashMap<Character, Integer> map = new HashMap<>();
char ch ='?';
        for(char c : chs){
if(map.get(c) == null)
map.put(c,1);
else{
int cnt = Integer.valueOf(map.get(c));
map.put(c,cnt+1);
if(cnt+1==2){
System.out.println(c);
                    ch = c;
break;
}
}
}
return ch;
}
}

发表于 2017-11-02 15:09:31 回复(0)

Java

剩一口

import java.util.*;

public class FirstRepeat {

public char findFirstRepeat(String A, int n) {

int[] num = new int[100];

char[] a= A.toCharArray();

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

num[a[i]-'0']++;

if(num[a[i]-'0']==2)

return a[i];

}

return ' ';

}

发表于 2017-08-27 16:29:14 回复(0)

Java

马卡维奇

     /**
     * 此题题目有些模棱两可，将题目的字符串都理解成字符串流更好一点。
     * 即从一个字符串流中，找出第一个重复的字符，这样表述就可以方便大家理解。
     * 理解简单遍历字符串并不可行。会采用Hash来做。
     */
    public char findFirstRepeat(String A, int n) {
        // write code here
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < A.length(); i++) {
            if (!set.add(A.charAt(i)))
                return A.charAt(i);
        }
        return ' ';
    }

发表于 2017-08-03 16:51:43 回复(0)

Java

我的Offer呢！

import java.util.*;
public class Coder {
	public String[] findCoder(String[] A, int n) {
		  Arrays.sort(A, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				return (o2.length() - o2.toLowerCase().replace("coder", "").length()) / "coder".length()
						- (o1.length() - o1.toLowerCase().replace("coder", "").length()) / "coder".length();
			}
		});
		  return  A;
	}
}

排序的依据是包含coder字符串的个数，进行升序排序，

因此利用这个条件，将coder全部替换为空串,

包含"coder"数量就是 (减少的字符数 / 5);

编辑于 2017-06-10 23:59:17 回复(0)

Java

QueenaGY

import java.util.*;

public class FirstRepeat {

public char findFirstRepeat(String A, int n) {

char[] ch = A.toCharArray();

List<Character> list = new ArrayList<Character>();

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

if(list.contains(ch[i]))

return ch[i];

else

list.add(ch[i]);

}

return '\0';

}

发表于 2017-04-11 13:48:35 回复(0)

Java

牛客753137号

import java.util.*;

public class FirstRepeat {
    public char findFirstRepeat(String A, int n) {
        if(A == null || n<2) return ' ';
        Map<Character,Integer> map = new HashMap<Character, Integer>();
        n = A.length();
        int count = 1;
        char c = ' ';
        for (int i=0; i< n; ++i){
            if(map.containsKey(A.charAt(i))) {
                c = A.charAt(i);
                break;
            }
            else
                map.put(A.charAt(i),count);
        }
        return c;

    }
}

编辑于 2017-03-31 22:29:52 回复(0)

Java

量子幽灵

import java.util.*;

public class FirstRepeat {

public char findFirstRepeat(String A, int n) {

return findSameChar(A, n);

}

public char findSameChar(String str, int len){

for(int i = 0 ; i <len - 1; ++i){

for(int j = i + 1; j < len; ++j){

if(str.charAt(i) == str.charAt(j)){

if(i + 1 == j)

return str.charAt(i);

else

return findSameChar(str.substring(i , j ), j - i);

}

return str.charAt(0);

}

发表于 2017-03-20 21:55:34 回复(0)

Java

熊熊我爱你天

public class FirstRepeat {
    public char findFirstRepeat(String A, int n) {
        // write code here
        boolean[] char_set = new boolean[256];
        for(int i = 0;i < n;i++){
            char val=A.charAt(i);
            if(char_set[val]){
                return val;
            }
            char_set[val]=true;
        }
        return ' ';
    }

}
第一种解法是构建一个布尔值的数组，索引i对应的标记指示该字符串是否含有子母表第i个字符，若是字符出现，则立即返回该字符。
第二种解法是用位向量。
public class FirstRepeat {
    public char findFirstRepeat(String A, int n) {
        // write code here
      int checker = 0;
        for(int i = 0;i < n;i++){
               int val=A.charAt(i)-'a';
            if((checker & (1<<val))>0){
                return A.charAt(i);
            }
            checker |= (1<<val);
        }
        return ' ';
    }
}

发表于 2017-03-14 10:18:04 回复(0)

Java

王小叶

//利用set，如果添加失败，表明重复
import java.util.*;

public class FirstRepeat {
    public char findFirstRepeat(String A, int n) {
        // write code here
        Set<Character> set = new HashSet<Character>();
        char[] ch = A.toCharArray();
        for(int i=0;i<ch.length;i++){
            if(!set.add(ch[i])){
                return ch[i];
            }
        }
        return ' ';
    }
}

发表于 2017-03-12 19:23:25 回复(0)

Java

Import4

//利用HashMap put()方法已有当前添加的键时返回原来的值，没有当前键则返回空的特性，将每个字符放入HashMap中判断是否不为为空

import java.util.*;

public class FirstRepeat {

public char findFirstRepeat(String A, int n) {

// write code here

int i;

HashMap<Integer,Integer> map=new HashMap();

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

if(map.put((int)A.charAt(i),1)!=null){

break;

}

return A.charAt(i);

}

发表于 2016-10-11 20:48:58 回复(0)

Java

Y.F.S.L.P.

import java.util.*;
public class FirstRepeat {
    public static char findFirstRepeat(String A, int n) {
        // write code here
        for(int i=0;i<n-1;i++){
            for(int j=i-1;j>=0;j--){
                if(A.charAt(i)==A.charAt(j)){
                   return A.charAt(i);
                }
            }
        }
       return '\0';
    }     
    public static void main(String [] args){
        Scanner in=new Scanner(System.in);
       // while(in.hasnext){
        String A=in.next();
        int n=in.nextInt();
       // }
          System.out.print(findFirstRepeat(A,n));
    }
}

发表于 2016-10-05 18:09:10 回复(0)

Java

沉、默

通过Set集合的无重复特性来解答

import java.util.*;

public class FirstRepeat {

public char findFirstRepeat(String A, int n) {

// write code here

char[] arr = A.toCharArray();

HashSet hs = new HashSet();

int count = -1;

char c = 0;

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

hs.add(arr[i]);

count++;

if(hs.size()==count){

c =arr[i];

break;

}

return c;

}

发表于 2016-09-22 21:49:22 回复(0)

Java

牛客346593号

public char findFirstRepeat(String A, int n) {
        // write code here
        Set<Character> set = new HashSet<Character>();
        char[] chars = A.toCharArray();
        for(char c : chars) {
            if(set.contains(c)) {
                return c;
            } else {
                set.add(c);
            }
        }
        return '\0';
}

发表于 2016-09-22 13:03:57 回复(0)

Java