题解 | #数组中只出现一次的数(其它数出现k次)#

数组中只出现一次的数(其它数出现k次)

http://www.nowcoder.com/practice/5d3d74c3bf7f4e368e03096bb8857871

package org.example.test;

import java.util.HashMap;
import java.util.Map;

public class BitTest {

    public static void main(String[] args) {
        int[] nums = {5, 4, 1, 1, 5, 1, 5};
        foundOnceNumber1(nums, 3);
        System.out.println(1 << 5);
    }

    /**
     * 暴力算法
     *
     * @param arr
     * @param k
     * @return
     */
    public int foundOnceNumber(int[] arr, int k) {
        // write code here
        Map<Integer, Integer> map = new HashMap<>();
        for (int value : arr) {
            if (map.get(value) == null) {
                map.put(value, 1);
            } else {
                map.put(value, map.get(value) + 1);
            }
        }
        for (Integer key : map.keySet()) {
            if (map.get(key) == 1) {
                return key;
            }
        }
        return -1;
    }

    /**
     * i
     * 3 2 1
     * 1 0 1
     * 1 0 1
     * 1 0 1
     * 1 0 0
     * 0 0 1
     * 0 0 1
     * 0 0 1
     * <p>
     * i=1: 6%3=0
     * i=2:
     * i=3: 4%3=1
     * 如果 == 1, 表示只出现一次的数这个i为是1,遍历32位,结果相加则为只出现一次的数
     *
     * @param arr
     * @param k
     * @return
     */
    public static int foundOnceNumber1(int[] arr, int k) {
        if (arr == null || arr.length <= 0) {
            return 0;
        }
        int result = 0;
        for (int i = 0; i <= 31; i++) {
            int curBitCnt = 0;
            for (int num : arr) {
                if ((num >> i & 1) != 0) {
                    curBitCnt++;
                }
            }
            if (curBitCnt % k == 1) {
                result += 1 << i;
            }
        }
        return result;
    }
}
算法 文章被收录于专栏

数据结构和算法

全部评论

相关推荐

不愿透露姓名的神秘牛友
11-26 18:54
说等下个版本吧的发呆爱好者很贪睡:佬最后去了哪家呀
点赞 评论 收藏
分享
沉淀一会:1.同学你面试评价不错,概率很大,请耐心等待; 2.你的排名比较靠前,不要担心,耐心等待; 3.问题不大,正在审批,不要着急签其他公司,等等我们! 4.预计9月中下旬,安心过节; 5.下周会有结果,请耐心等待下; 6.可能国庆节前后,一有结果我马上通知你; 7.预计10月中旬,再坚持一下; 8.正在走流程,就这两天了; 9.同学,结果我也不知道,你如果查到了也告诉我一声; 10.同学你出线不明朗,建议签其他公司保底! 11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
评论
1
收藏
分享
正在热议
# 25届秋招总结 #
440577次浏览 4493人参与
# 春招别灰心,我们一人来一句鼓励 #
41484次浏览 524人参与
# 北方华创开奖 #
107302次浏览 599人参与
# 地方国企笔面经互助 #
7928次浏览 18人参与
# 同bg的你秋招战况如何? #
75577次浏览 552人参与
# 虾皮求职进展汇总 #
114215次浏览 884人参与
# 阿里云管培生offer #
119843次浏览 2219人参与
# 实习,投递多份简历没人回复怎么办 #
2454001次浏览 34848人参与
# 实习必须要去大厂吗? #
55678次浏览 960人参与
# 提前批简历挂麻了怎么办 #
149825次浏览 1977人参与
# 投递实习岗位前的准备 #
1195707次浏览 18546人参与
# 你投递的公司有几家约面了? #
33178次浏览 188人参与
# 双非本科求职如何逆袭 #
661910次浏览 7394人参与
# 如果公司给你放一天假,你会怎么度过? #
4730次浏览 55人参与
# 机械人春招想让哪家公司来捞你? #
157604次浏览 2267人参与
# 如果你有一天可以担任公司的CEO,你会做哪三件事? #
11365次浏览 270人参与
# 发工资后,你做的第一件事是什么 #
12418次浏览 61人参与
# 工作中,努力重要还是选择重要? #
35612次浏览 384人参与
# 参加完秋招的机械人,还参加春招吗? #
20091次浏览 240人参与
# 我的上岸简历长这样 #
451924次浏览 8088人参与
# 实习想申请秋招offer,能不能argue薪资 #
39235次浏览 314人参与
# 非技术岗是怎么找实习的 #
155850次浏览 2120人参与
牛客网
牛客企业服务