[问题:]
Given an array of integers, every element appearstwiceexcept
for one. Find that single one.
Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
翻译:给定一个整数数组,数组中所有元素都出现了两次,只有一个元素只出现了一次,找出这个只出现了一次的元素。
[
解法:]
①. 常规解法:时间复杂度为O(n²),没能通过
/**
* Time Limit Exceeded
* 时间复杂度为:O(n²),无法通过
*/
public class Solution1 {
public int singleNumber(int[] arr) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if (arr[i] == arr[j]) {
count++;
}
}
if (count == 1) {
return arr[i];
} else {
count = 0;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = { 0, 1, 1, 2, 2, 3, 0 };
System.out.println(new Solution1().singleNumber(arr));
}
}
②. 标准解法:使用异或运算
这个程序用了个小技巧:一个整数和它本身异或之后得到值是0,0与其他整数异或得到的是这个整数本身
/**
* 利用异或的可交换性
*/
public class Solution2 {
public int singleNumber(int[] arr) {
// invalid check
if (arr.length == 0) {
return -1;
}
int result = 0;
for (int i = 0; i < arr.length; i++) {
result = result ^ arr[i];
}
return result;
}
public static void main(String[] args) {
int[] arr = { 0, 1, 1, 2, 2, 3, 0 };
System.out.println(new Solution2().singleNumber(arr));
}
}
[ 拓展:]
异或运算的两个法则:
①.a ^ b = b ^ a
②. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
真^
假 = 真 假^
真 = 真 假^ 假
= 假 真^ 真 = 假
/**
* 不使用第三个变量,交换两个变量的值
*/
public class Swap {
public static void main(String[] args) {
int a = 1, b = 2;
System.out.println("交换前: a = " + a + " , b = " + b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("交换后: a = " + a + " , b = " + b);
}
}
分享到:
相关推荐
Java-Leetcode-乘积最大子数组.zip
题目链接难度:简单 类型: 数组、二分法我们把符合下列属性的数组 A 称作山脉:给定一个确定为山脉的数组,返回任何满足 A[0] [1]
示例1输出:[0,2,1,-6,6,-7,9,1,2,0,1]解释:0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1示例2输
扩展二:给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。中每一位二进制位1出
请你找出并返回数组中的 最小元素 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1: 输入:nums = [3,4,5,1,2] 输出:1 解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
示例 1:输入: [2,2,1]输出: 1示例 2:输入: [4,1,2,1,2]输出: 41、思路自己想的思路,很简单,创建一个字典,循环整个数组,如果该值出
示例输出:4解释:有 4 组好数对,分别是 (0,3), (0,4), (3,4), (2,5) ,下标从 0 开始解题思路只要想到用一个二维数组的方式来判断就
leetcode 答案解析 golang解答
leetcode 答案 private leetcode algorithm exercises for array 注意,很多题目标签是有多个的,所以这个array标签的题可能和其他的题会有重复的部分 // 用寒假的时间,尽量把leetcode多刷一点。由于刚开始刷,可以...
leetcode卡数组-LeetCode-解决方案 这个存储库包含我对数据结构介绍数组小节中问题的解决方案@leetcode.com - 问题链接: -查看我对 leetcode 可能挑战的解决方案:
示例 1:输出:2解释:数组中唯一的幸运数是 2 ,因为数值 2 的出现频次也是 2 。示例 2:输出:3解释:1、2 以及 3 都是幸运数,只需要返回其中最大
leetcode思维导图-数组
nums,就地删除重复项,以便每个元素只出现一次并返回新的长度。 不要为另一个数组分配额外的空间,您必须通过使用 O(1) 额外内存就地修改输入数组来实现。 在这个问题中,要关注的关键点是正在排序的输入数组。 就...
leetcode-链表笔记
要求:构建一个长度为 2 * n 的答案数组 ans,数组下标从 0 开始计数 ,对于所有 0 的 i ,满足下述所有要求:具体而言,ans
1、num和数组下标index有一一映射关系 2、使用*(-1)的方式,好处在于判断信息不会额外占用空间,并且使用Math.abs可以解析原有的num信息 3、
leetcode 答案leetcode-问题--数组 这些文件是leetcode中数组相关问题的解答
970. 强整数对数运算function powerfulIntegers(x: number, y: number, bound: number): numb
leetcode-cn.go 数组 267 动态规划 213 数学 190 字符串 187 树 155 深度优先搜索 132 哈希表 132 二分查找 92 贪心算法 78 广度优先搜索 74 双指针 70 栈 64 并查集 30 分治算法 28 Sliding Window 24 递归 23 字典...
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明:你可以假设 k 总是有效...