leetcode-448-461

leetcode 448题 461题

leetcode 448题题目:

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:[4,3,2,7,8,2,3,1]

输出:[5,6]

解答:

思路:第一个for循环相当于是将输入数组中,与数组中元素值-1对应位置的数加上数组长度,那么循环结束之后,如果某个位置上的元素值是大于数组长度的,那么代表这个位置上有相应的元素出现,如果是小于或等于的,那么代表没有相应的元素出现。那么返回这个位置值+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
var findDisappearedNumbers = function(nums) {
for(var i=0;i<nums.length;i++){
var index = (nums[i]-1)%nums.length;
nums[index] = nums[index] + nums.length;
}
var res = [];
for(var i=0;i<nums.length;i++){
if(nums[i]<=nums.length){
res.push(i+1);
}
}
return res;
};

leetcode 461题题目:

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y,计算它们之间的汉明距离。

示例

解答:

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
//这种方法空间复杂度太高
var hammingDistance = function(x, y) {
var str1 = x.toString(2);
var str2 = y.toString(2);
var arr1 = str1.split('');
var arr2 = str2.split('');
var len = Math.max(arr1.length,arr2.length);
var dis;
if(len>arr1.length){
dis = len - arr1.length;
while(dis--){
arr1.unshift(0);
}
}else{
dis = len - arr2.length;
while(dis--){
arr2.unshift(0);
}
}
var count = 0;
for(var i=0;i<arr1.length;i++){
if(arr1[i]!=arr2[i]){
count++;
}
}
return count;
};
1
2
3
4
5
6
7
8
9
10
11
12
//空间复杂度低的方法
var hammingDistance = function(x, y) {
x = x^y;//x与y的异或
var count = 0;
while(x!=0){
if(x%2==1){
count++;
}
x>>=1;
}
return count;
};
分享到