FilesExpand file tree

 master

/

offer502.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

71 lines (65 loc) · 2.66 KB

 master

/

offer502.java

Copy path

Top

File metadata and controls

• Code
• Blame

71 lines (65 loc) · 2.66 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

import java.util.ArrayDeque;

import java.util.Queue;

/**

* [50-II] 字符流中第一个不重复的字符

*

* 题目: 实现一个函数用来找出字符流中第一个只出现一次的字符. 如果当前字符流没有存在出现一次的字符, 返回 '#' 字符.

*

* 思路: 1. 用数组存储每个从数据流中读取的字符的索引(从 1 开始, 0 代表当前字符未出现过; 不同字符使用 ascii码 一一映射到整数数组中).

* 当字符重复出现时, 将数组中的值置为 -1. 这样数组中就保存了只出现一次的字符的索引, 遍历数组找到第一个只出现一次的字符.

* 2. 用数组统计从字符流中读取的每个字符的出现次数(不同字符使用 ascii码 一一映射到整数数组中), 并将遍历到的字符依次加入到队列中.

* 不断维护队首元素为第一个只出现一次的字符(不断出队出现多次的字符).

*/

public class Solution {

/**

* 方法一

*/

private int[] occurrence = new int[128];

// index is the index of current character in stringstream.

private int index = 1;

//Insert one char from stringstream

public void Insert1(char ch) {

// record current character's first appeared index in stringstream.

// if current character appeared one more time, record -1 for mark.

if (occurrence[ch] == 0) {

occurrence[ch] = index;

} else if (occurrence[ch] > 0) {

occurrence[ch] = -1;

}

// move index to point next character.

index++;

}

//return the first appearence once char in current stringstream

public char FirstAppearingOnce1() {

char res = '#';

int minIndex = Integer.MAX_VALUE;

// traverse occurrence array for find earliest index of char which appear only one time

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

if (occurrence[i] > 0 && occurrence[i] < minIndex) {

res = (char) i;

minIndex = occurrence[i];

}

}

return res;

}

/**

* 方法二

*/

private int[] cnts = new int[128];

private Queue<Character> queue = new ArrayDeque<>();

//Insert one char from stringstream

public void Insert(char ch)

{

cnts[ch]++;

queue.offer(ch);

// maintenance queue head element is the character which first appear only one time.

while (!queue.isEmpty() && cnts[queue.peek()] > 1) {

queue.poll();

}

}

//return the first appearence once char in current stringstream

public char FirstAppearingOnce()

{

return queue.isEmpty() ? '#' : queue.peek();

}

}