By

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考

题目

a~z 包括大小写与 0~9 组成的 N 个数, 用最快的方式把其中重复的元素挑出来。

解析

本题中已经限制了可能出现字符,他们对应的ascii为

  • a-z:97~122,
  • A-Z:65-90
  • 0-9:48~57

所以这里只需要用位图法来存储，并且之用128位即可，就是4个长度的int数组，
在操作过程中，如果数组中已经设置了值，则说明当前遍历的为重复，打印出来即可
否则，将这个值设置到数组中，整体思路与位排序大致一致，复杂度为O(n)

代码

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
public static void findSameChar(String str)
{
	int[] store=new int[4];//4*32 =128  已经可以存下a~z大小写以及0~9
	for(int i=0;i<str.length();i++)
	{
		if(get(store,(int)str.charAt(i))>0)
		{//表示这里已经设置过值了，直接打印出来即可
			System.out.print(str.charAt(i));
		}else{//未出现过，需要先设置标志一下
			set(store,(int)str.charAt(i));
		}
	}
}

//11111
private static final int SHIFT=5;//除以32
private static final int MASK=0x1F;//向32取余
public static int get(int[] a,int v)
{
	return a[v>>SHIFT]&(1<<(v&MASK));
}

public static void set(int[] a,int v)
{
	a[v>>SHIFT]|=(1<<(v&MASK));
}

看下实验结果：

1
2
3
4
5
public static void main(String args[])
{
	String str="helloworld1232";
	findSameChar(str);
}

lol2

参考

  • July 微软面试100题 第84.1题

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考