记录：2022-9-17 数组中重复的数据 丑数 II 文件分配方式 位图及使用（打卡）_位图打卡

学习时间：2022-9-17

学习内容

1、leetcode

442. 数组中重复的数据

采用原地Hash的方式做，代码如下：

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ans = new ArrayList<Integer>();
        for(int i = 0;i<nums.length;i++){
            int value = nums[i];
            int index = value-1;
            if(index == i){
                continue;
            }
            if(nums[i] == nums[index]){
                continue;
            }
            swap(nums,i,index);
            i--;
        }
        for(int i = 0;i<nums.length;i++){
            //找下标
            if(i != nums[i]-1){
                ans.add(nums[i]);
            }
        }
        return ans;
    }
    public void swap(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
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

264. 丑数 II

使用动态规划+三指针法（多路归并），最优子结构为：

dp[i] = Math.min(Math.min(num2,num3),num5);

class Solution {
    public int nthUglyNumber(int n) {
        int ptr2 = 1;
        int ptr3 = 1;
        int ptr5 = 1;
        int[] dp = new int[n+1];
        dp[1] = 1;
        for(int i = 2;i<=n;i++){
            int num2 = dp[ptr2]*2;
            int num3 = dp[ptr3]*3;
            int num5 = dp[ptr5]*5;
            dp[i] = Math.min(Math.min(num2,num3),num5);
            if(dp[i] == num2){
                ptr2++;
            }
            if(dp[i] == num3){
                ptr3++;
            }
            if(dp[i] == num5){
                ptr5++;
            }
        }
        return dp[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

2、文件分配

文件分配给磁盘有三种分配方式：连续分配|链接分配|索引分配

连续分配

对标数组中查找、新增元素
寻道时间最短 访问容易 有大量外部碎片产生（内存的特性）
解决方案为合并磁盘空间，但是这样就算解决了外部碎片，开销也过于大

链接分配

对标链表中查找、新增元素
寻道时间比较长（磁头寻道时间较长）
创建指针会有单独的内存开销
没有外部碎片
解决开销问题：将多个块组成簇，这种方法会增加内部碎片

索引分配

对标hash表中查找、新增元素
通过加大空间消耗来使链接分配的方式折中寻道时间（增加索引块）
但是索引块对空间的占用比较大
另外对索引块大小也有考究，不能过小或过大
目前的链接目的有：把索引块做成链接块，本身就可以读的话，就可以减少专门作索引块的压力
使用多级索引

3、位图概念及redis中位图的使用

位图，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。
举个例子，如下图，如果我们想要存放 0,2,4,5,10,11,12,14,15这几个数字，如果采用普通存储方式，若4位表示一个数字，这9个数字需要4*9=36位，至少36位才能存储这些数据。

如果采用位图的方式，只需要上图的16位就能存储这9个数字。
查找的时候，只需要查找这个位的数是1还是0即可，就可以确定该数存在不存在。
当数量足够大时候，不光大大压缩了存储空间，查找速率也极快，可以说是O(1)。

bitmap是redis的一种扩展数据类型，主要用于二值状态统计，比如公司记录员工打卡记录，电商网站记录用户登录行为，积分商城记录用户签到情况。

例子转自知乎：redis灵魂拷问：聊一聊bitmap使用

下面我们看一下bitmap的使用。

员工打卡
假如一个公司有100个员工，公司要对员工11月份的打卡行为进行统计，我们可以为11月份每一天分配一个bitmap，这个bitmap保存100个bit位，来记录员工的打卡行为。

注意:bitmap偏移量从0开始，所以100个bit位是从0~99，依次记录1-100号员工。

我们定义bitmap的key格式为:signed:20201101，记录2020年11月1日的打卡情况。下面代码是员工打卡和查询员工打卡情况：

/**
 * SETBIT命令
 * 员工打卡
 * 时间复杂度：O(1)
 */
public void sign(String key, int employeeNumber){
    redisTemplate.opsForValue().setBit(key, employeeNumber - 1, true);
}

/**
 * GETBIT命令
 * 查看员工打卡情况
 * 时间复杂度：O(1)
 */
public boolean isSigned(String key,int employeeNumber){
    return redisTemplate.opsForValue().getBit(key, employeeNumber - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

我们可以查看某一天的打卡总人数，代码如下，入参：“signed:20201101”：

/**
 * BITCOUNT命令
 * 查看某一天的打卡人数
 * 时间复杂度：O(N)
 */
public Long signedCount(String key){
    return (Long) redisTemplate.execute((RedisCallback<Long>)  conn -> conn.bitCount(key.getBytes()));
}
1
2
3
4
5
6
7
8

那如果想看当月没有迟到过的员工呢？这个时候就要用到交集了，对当月每天的bitmap做交集，值为1的员工就是没有迟到过的。

这时就要用到bitmap的聚合运算了，命令BITOP， 支持AND(与)、OR(或), XOR(异或) and NOT(非)运算，除了NOT后面跟一个bitmap外，其他3种聚合运算后面都可以跟多个bitmap，命令如下：

BITOP AND destkey srckey1 srckey2 srckey3 … srckeyN
BITOP OR destkey srckey1 srckey2 srckey3 … srckeyN
BITOP XOR destkey srckey1 srckey2 srckey3 … srckeyN
BITOP NOT destkey srckey

bitmap广泛地运用在二值计算的场景，对于一个二值状态只用一个bit位就可以，非常节约内存。比如我们对一个10亿的用户进行日活计算，占用的空间为10亿/8/1024/1024=120M