剑指offer(一)-数组

数组中只出现一次的两个数字

一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

示例

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

返回值:
[4,6]

说明:
返回的结果中较小的数排在前面

分析

方法一通过哈希表,若出现一次则+1,最后遍历查询值等于一的数字,输出排序后的数组即可。

方法二可以通过查找数组中每个数字第一次出现的位置和最后一次出现的位置是否匹配来确定是否只出现一次,最后再去重排序即可。

解答

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
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
function FindNumsAppearOnce( array ) {
let map = {};
let result = [];
for(let i = 0; i< array.length;i++){
//方法一
if(map[array[i]])
map[array[i]]++
else
map[array[i]] = 1;
//方法二
if(array.indexOf(array[i]) === array.lastIndexOf(array[i]))
result.push(array[i]);
}
//方法一
for(let num in map){
if(map[num] === 1)
result.push(num);
}
//方法二
result = [...new Set(result)];//去重
return result.sort((a,b) => a-b);;
}
module.exports = {
FindNumsAppearOnce : FindNumsAppearOnce
};

数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例:

1
2
3
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3

分析

将数组排序,遍历排序后的数组,若出现连续相同的数字,则为重复的数字

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* @param {number[]} nums
* @return {number}
*/
var findRepeatNumber = function(nums) {
nums.sort((a,b)=>a-b);
for(let i = 1;i<nums.length;i++){
if(nums[i] === nums[i-1]){
return nums[i]
}
}
return -1;
};

二维数组中的查找

在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

示例:

1
2
3
4
5
6
7
8
9
10
11
现有矩阵 matrix 如下:

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5,返回 true。
给定 target = 20,返回 false。

分析

方法一,使用方法flat()将二维数组展开,再使用include()方法查询是否存在整数

方法二,从左下角或右上角开始寻找, 如果元素相等则退出, 若不等,则根据大小按不同方向查找,即若从左下角开始,target大于当前位置,则向右,否则向上查。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var findNumberIn2DArray = function(matrix, target) {
//方法1
return matrix.flat(2).includes(target);
//方法2
if(!matrix || matrix.length == 0 || matrix[0].length == 0)
return false;
let i = matrix.length - 1,j=0;
while(i>=0 && j<matrix[0].length){
if(matrix[i][j] === target)
return true;
else if(matrix[i][j] > target){
i--;
}else if(matrix[i][j] < target){
j++;
}
}
return false;
};

在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

示例:

1
2
3
4
5
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

分析

查看该数字再数组中第一次indexOf()和最后一次出现的位置lastIndexOf(),若第一次出现的位置为-1,则不存在,否则lastIndexOf() - indexOf() + 1即为数字出现的次数

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
let index = nums.indexOf(target);
let lastIndex = nums.lastIndexOf(target);
if(index == -1)
return 0;
else
return lastIndex - index + 1;
};

构建乘积数组

给定一个数组 A[0,1,…,n-1],请构建一个数组 B[0,1,…,n-1],其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

1
2
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

分析

从两头遍历数组,先计算当前元素之前的乘积值,再计算当前元素之后的乘积值。两值相乘即为当前元素B[i]的值

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number[]} a
* @return {number[]}
*/
var constructArr = function(a) {
let result = [];
let right = 1;//当前元素后边的值
result[0] = 1;//A[0]的值
if(!a || !a.length)
return [];
for(let i = 1;i<a.length;i++){
result[i] = result[i-1] * a[i-1];//当前元素之前的乘积值
}
for(let j = a.length - 2;j>=0;j--){
right *= a[j+1];
result[j] *= right;
}
return result;
};

把数组排成最小的数

输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

示例:

1
2
3
4
5
输入: [10,2]
输出: "102"

输入: [3,30,34,5,9]
输出: "3033459"

分析

构造一个新的sort方法,若数组中数字位数相同,则按从小到大排列,若数组中位数不同,则查看两个数字合起来a+b/b+a哪个最小则按哪个排。

最后使用join()方法输出排序好的数组组成的字符串即可

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @return {string}
*/
var minNumber = function(nums) {
nums.sort((a,b)=>{
if(a.toString().length === b.toString().length)
return a-b;
else{
return parseInt(a.toString() + b.toString()) - parseInt(b.toString() + a.toString());
}

});
return nums.join("");
};

数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例:

1
2
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

分析

先将数组排序,再遍历数组查询每个数字第一次indexOf()和最后一次出现的位置lastIndexOf(),查看两者之差lastIndexOf() - indexOf() + 1,即出现的次数。

若出现的次数<数组长度的一半,则跳过,

若出现的次数>数组长度的一半,则与当前出现次数的最大值对比,存储更大的值。

最后输出出现次数最多的数字。

解答

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
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
nums.sort((a,b)=>{return a-b;});
let len = nums.length /2;
let max = 0;
let index = 0;
if(nums.length === 1)
return nums[0];
for(let i = 0;i<nums.length;i++){
let first = nums.indexOf(nums[i]);
let last = nums.lastIndexOf(nums[i]);
let dif = last - first + 1;
if(dif === 0 || dif <= len){
continue;
}else if(dif > len){
if(dif > max){
max = dif;
index = i;
}else{
continue;
}
return nums[index];
}
}
};

调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

示例:

1
2
3
输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。

分析

使用双指针从数组头尾开始搜索,若左边遇到偶数则与右边出现的奇数交换。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number[]} nums
* @return {number[]}
*/
var exchange = function(nums) {
let i=0,j=nums.length-1;
while(i<j){
while(nums[i]%2 === 1)
i++;
while(nums[j]%2 === 0)
j--;
if(i<j){

[nums[i],nums[j]] = [nums[j],nums[i]];

}
}
return nums;
};

寻找两个正序数组的中位数

给定两个大小分别为m和n的正序(从小到大)数组nums1和nums2。请你找出并返回这两个正序数组的中位数 。

1
2
3
4
5
6
7
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

分析

合并两个数组,并排序,若新数组长度为奇数,则中位数为其中间的一个值num[num.length/2]。若长度为偶数,则为中间两个数的平均值

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let num = nums1.concat(nums2);
if(num.length && num){
num.sort((a,b)=>{
return a-b;
});
let a = Math.floor(num.length / 2);
if(num.length % 2 === 0){
return (num[a] + num[a-1])/2;
}else{
return num[a];
}
}
};

和为S的两个数字

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

返回值描述:
对应每个测试案例,输出两个数,小的先输出。

示例

1
2
3
4
5
输入:
[1,2,4,7,11,15],15

返回值:
[4,11]

分析

循环遍历数组,计算和与当前元素的差,构建对象存储所有的差值,若当前差值存在,则计算差值和当前值的乘积,并与当前最小乘积对比,存储更小的值。若当前差值不存在,则将当前差值织wei

  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2020-2024 Aweso Lynn
  • PV: UV: