- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章海量数据去重排序bitmap(位图法)在java中实现的两种方法由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
在海量数据中查找出重复出现的元素或者去除重复出现的元素是面试中常考的文图。针对此类问题,可以使用位图法来解决。例如:已知某个文件内包含若干个电话号码,要求统计不同的号码的个数,甚至在o(n)时间复杂度内对这些号码进行排序.
位图法需要的空间很少(依赖于数据分布,但是我们也可以通过一些放啊发对数据进行处理,使得数据变得密集),在数据比较密集的时候效率非常高。例如:8位整数可以表示的最大十进制数值为99999999,如果每个数组对应于一个bit位,那么把所有的八进制整数存储起来只需要:99mbit = 12.375mb. 。
实际上,java jdk1.0已经提供了bitmap的实现bitset类,不过其中的某些方法是jdk1.4之后才有的.
下面我先自己实现一下bitmap 的原理,然后再直接调用jdk的bitset类分别实现bitmap, 方便比较理解:
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
72
73
74
75
76
77
78
79
80
81
|
package
swordoffer;
//去除重复并排序
import
java.util.arrays;
import
java.util.bitset;
import
java.util.random;
/**
* @author gavenyeah
* @date time:
* @des:
*/
public
class
bitmap {
int
arrnum =
800
;
int
len_int =
32
;
int
mmax =
9999
;
int
mmin =
1000
;
int
n = mmax - mmin +
1
;
public
static
void
main(string args[]) {
new
bitmap().findduplicate();
new
bitmap().finddup_jdk();
}
public
void
finddup_jdk() {
system.out.println(
"*******调用jdk中的库方法--开始********"
);
bitset bitarray =
new
bitset(n);
int
[] array = getarray(arrnum);
for
(
int
i =
0
; i < arrnum; i++) {
bitarray.set(array[i] - mmin);
}
int
count =
0
;
for
(
int
j =
0
; j < bitarray.length(); j++) {
if
(bitarray.get(j)) {
system.out.print(j + mmin +
" "
);
count++;
}
}
system.out.println();
system.out.println(
"排序后的数组大小为:"
+ count );
system.out.println(
"*******调用jdk中的库方法--结束********"
);
}
public
void
findduplicate() {
int
[] array = getarray(arrnum);
int
[] bitarray = setbit(array);
printbitarray(bitarray);
}
public
void
printbitarray(
int
[] bitarray) {
int
count =
0
;
for
(
int
i =
0
; i < n; i++) {
if
(getbit(bitarray, i) !=
0
) {
count++;
system.out.print(i + mmin +
"\t"
);
}
}
system.out.println();
system.out.println(
"去重排序后的数组大小为:"
+ count);
}
public
int
getbit(
int
[] bitarray,
int
k) {
// 1右移 k % 32位 与上 数组下标为 k/32 位置的值
return
bitarray[k / len_int] & (
1
<< (k % len_int));
}
public
int
[] setbit(
int
[] array) {
// 首先取得数组位置下标 i/32, 然后 或上
// 在该位置int类型数值的bit位:i % 32
int
m = array.length;
int
bit_arr_len = n / len_int +
1
;
int
[] bitarray =
new
int
[bit_arr_len];
for
(
int
i =
0
; i < m; i++) {
int
num = array[i] - mmin;
bitarray[num / len_int] |= (
1
<< (num % len_int));
}
return
bitarray;
}
public
int
[] getarray(
int
arrnum) {
@suppresswarnings
(
"unused"
)
int
array1[] = {
1000
,
1002
,
1032
,
1033
,
6543
,
9999
,
1033
,
1000
};
int
array[] =
new
int
[arrnum];
system.out.println(
"数组大小:"
+ arrnum);
random r =
new
random();
for
(
int
i =
0
; i < arrnum; i++) {
array[i] = r.nextint(n) + mmin;
}
system.out.println(arrays.tostring(array));
return
array;
}
}
|
总结 。
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我的支持。如果你想了解更多相关内容请查看下面相关链接 。
原文链接:https://blog.csdn.net/y999666/article/details/51220833 。
最后此篇关于海量数据去重排序bitmap(位图法)在java中实现的两种方法的文章就讲到这里了,如果你想了解更多关于海量数据去重排序bitmap(位图法)在java中实现的两种方法的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
初学者 android 问题。好的,我已经成功写入文件。例如。 //获取文件名 String filename = getResources().getString(R.string.filename
我已经将相同的图像保存到/data/data/mypackage/img/中,现在我想显示这个全屏,我曾尝试使用 ACTION_VIEW 来显示 android 标准程序,但它不是从/data/dat
我正在使用Xcode 9,Swift 4。 我正在尝试使用以下代码从URL在ImageView中显示图像: func getImageFromUrl(sourceUrl: String) -> UII
我的 Ubuntu 安装 genymotion 有问题。主要是我无法调试我的数据库,因为通过 eclipse 中的 DBMS 和 shell 中的 adb 我无法查看/data/文件夹的内容。没有显示
我正在尝试用 PHP 发布一些 JSON 数据。但是出了点问题。 这是我的 html -- {% for x in sets %}
我观察到两种方法的结果不同。为什么是这样?我知道 lm 上发生了什么,但无法弄清楚 tslm 上发生了什么。 > library(forecast) > set.seed(2) > tts lm(t
我不确定为什么会这样!我有一个由 spring data elasticsearch 和 spring data jpa 使用的类,但是当我尝试运行我的应用程序时出现错误。 Error creatin
在 this vega 图表,如果我下载并转换 flare-dependencies.json使用以下 jq 到 csv命令, jq -r '(map(keys) | add | unique) as
我正在提交一个项目,我必须在其中创建一个带有表的 mysql 数据库。一切都在我这边进行,所以我只想检查如何将我所有的压缩文件发送给使用不同计算机的人。基本上,我如何为另一台计算机创建我的数据库文件,
我有一个应用程序可以将文本文件写入内部存储。我想仔细看看我的电脑。 我运行了 Toast.makeText 来显示路径,它说:/数据/数据/我的包 但是当我转到 Android Studio 的 An
我喜欢使用 Genymotion 模拟器以如此出色的速度加载 Android。它有非常好的速度,但仍然有一些不稳定的性能。 如何从 Eclipse 中的文件资源管理器访问 Genymotion 模拟器
我需要更改 Silverlight 中文本框的格式。数据通过 MVVM 绑定(bind)。 例如,有一个 int 属性,我将 1 添加到 setter 中的值并调用 OnPropertyChanged
我想向 Youtube Data API 提出请求,但我不需要访问任何用户信息。我只想浏览公共(public)视频并根据搜索词显示视频。 我可以在未经授权的情况下这样做吗? 最佳答案 YouTube
我已经设置了一个 Twilio 应用程序,我想向人们发送更新,但我不想回复单个文本。我只是想让他们在有问题时打电话。我一切正常,但我想在发送文本时显示传入文本,以确保我不会错过任何问题。我正在使用 p
我有一个带有表单的网站(目前它是纯 HTML,但我们正在切换到 JQuery)。流程是这样的: 接受用户的输入 --- 5 个整数 通过 REST 调用网络服务 在服务器端运行一些计算...并生成一个
假设我们有一个名为 configuration.js 的文件,当我们查看内部时,我们会看到: 'use strict'; var profile = { "project": "%Projec
这部分是对 Previous Question 的扩展我的: 我现在可以从我的 CI Controller 成功返回 JSON 数据,它返回: {"results":[{"id":"1","Sourc
有什么有效的方法可以删除 ios 中 CBL 的所有文档存储?我对此有疑问,或者,如果有人知道如何从本质上使该应用程序像刚刚安装一样,那也会非常有帮助。我们正在努力确保我们的注销实际上将应用程序设置为
我有一个 Rails 应用程序,它与其他 Rails 应用程序通信以进行数据插入。我使用 jQuery $.post 方法进行数据插入。对于插入,我的其他 Rails 应用程序显示 200 OK。但在
我正在为服务于发布请求的 API 调用运行单元测试。我正在传递请求正文,并且必须将响应作为帐户数据返回。但我只收到断言错误 注意:数据是从 Azure 中获取的 spec.js const accou
我是一名优秀的程序员,十分优秀!