剑指Offer JavaScript-数组专题
二维数组中的查找
1. 题目描述
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
2. 解题思路
时间复杂度是 $O(N)$，空间复杂度是$O(1)$
利用数组的排序性质：如果要查找的元素小于当前元素，那么一定不在当前元素左边的列；如果要查找的元素大于当前元素，那么一定在当前元素下面的行。
3. 代码
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
33
34
35
36
37
38
39
40
41
42
/**
* 题目答案
* @param {Array} arr
* @param {Number} elem
*/
function findElem(arr, elem) {
let row = arr.length - 1,
col = arr[0].length - 1;
let i = 0,
j = col;
while (i <= row && j >= 0) {
if (arr[i][j] === elem) {
return true;
}
if (elem > arr[i][j]) {
++i;
} else {
--j;
}
}
return false;
}
/**
* 以下是测试代码
*/
const arr = [
[1, 2, 8, 9],
[2, 4, 9, 12],
[4, 7, 10, 13],
[6, 8, 11, 15],
];
console.log(findElem(arr, 8));
console.log(findElem(arr, 1));
console.log(findElem(arr, 145));
数组顺序调整
1. 题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
2. 思路描述
这题进一步抽象就是满足一定条件的元素都移动到数组的前面，不满足的移动到后面。所以，需要有一个参数用来传递判断函数。
最优解法就是数组两头分别有一个指针，然后向中间靠拢。符合条件，就一直向中间移动；不符合条件，就停下来指针，交换两个元素；然后继续移动，直到两个指针相遇。
3. 代码实现
函数change运用了设计模式中的“桥接模式”，判断条件由用户自己定义。
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
33
34
35
36
37
38
39
/**
* 交换数组元素
* @param {Array} arr
* @param {Number} i
* @param {Number} j
*/
const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
/**
* 将符合compareFn要求的数据排在前半部分，不符合要求的排在后半部分
* @param {Array} brr
* @param {Function} compareFn
* @return {Array}
*/
function change(brr, compareFn) {
const arr = [...brr],
length = brr.length;
let i = 0,
j = arr.length - 1;
while (i < j) {
while (i < length && compareFn(arr[i])) ++i;
while (j >= 0 && !compareFn(arr[j])) --j;
if (i < j) {
swap(arr, i, j);
++i;
--j;
}
}
return arr;
}
/**
* 测试代码
*/
const isOdd = (num) => (num & 1) === 1;
console.log(change([1, 2, 3, 4], isOdd));
把数组排成最小的数
1. 题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为 321323。
2. 思路分析
因为涉及拼接，所以可以将其看做字符串，同时规避了大数溢出的问题，而且字符串的比较规则和数字相同。
借助自定义排序，可以快速比较两个数的大小。比如只看{3, 32}这两个数字。它们可以拼接成 332 和 323，按照题目要求，这里应该取 323。也就是说，此处自定义函数应该返回-1。
3. 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
*
* @param {Array} numbers
*/
function printMinNumber(numbers) {
numbers.sort((x, y) => {
const s1 = x + "" + y,
s2 = y + "" + x;
if (s1 < s2) return -1;
if (s1 > s2) return 1;
return 0;
});
console.log(numbers.join(""));
}
/**
* 测试代码
*/
printMinNumber([3, 32, 321]);
数组中的逆序对
1. 题目描述
输入一个数组,求出这个数组中的逆序对的总数。
例如在数组{7，5，6，4}中，一共存在 5 个逆序对，分别是(7,6), (7, 5), (7,4), (6,4), (5,4)。
2. 思路分析
暴力法的时间复杂度是 O(N^2)。利用归并排序的思路，可以将时间复杂度降低到 O(NlogN)。
比如对于 7、5、6、4 来说，会被分成 5、7 和 4、6 两组。
准备两个指针指向两组最后元素，当左边数组指针的对应元素小于右边指针对应元素，结果可以加上从左指针到右指针之间的元素个数（都是逆序的）。
依次移动指针，直到达到边界。
3. 代码实现
代码最后输出了数组，经过归并，数组已经是有序的了。
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
*
* @param {Array} arr
* @param {Number} start
* @param {Number} end
* @return {Number}
*/
function findInversePairNum(arr, start, end) {
if (start === end) {
return 0;
}
const copy = new Array(end - start + 1);
const length = (end - start) >> 1;
const leftNum = findInversePairNum(arr, start, start + length);
const rightNum = findInversePairNum(arr, start + length + 1, end);
let i = start + length, // 左子数组的最后一个下标
j = end, // 右子数组的最后一个下标
count = leftNum + rightNum,
copyIndex = end - start; // copy数组中的最后一个下标
// 可以参考数据集合：[2, 3, 1, 4]
for (; i >= start && j >= start + length + 1; ) {
if (arr[i] > arr[j]) {
copy[copyIndex--] = arr[i--];
count += j - start - length;
} else {
copy[copyIndex--] = arr[j--];
}
}
for (; i >= start; --i) {
copy[copyIndex--] = arr[i];
}
for (; j >= start + length + 1; --j) {
copy[copyIndex--] = arr[j];
}
// 将排序号的数据放到原数组中
for (i = 0; i < end - start + 1; ++i) {
arr[i + start] = copy[i];
}
// clear
copy.length = 0;
return count;
}
/**
* 测试代码
*/
const arr = [7, 5, 6, 4];
console.log(findInversePairNum(arr, 0, arr.length - 1)); // output: 5
console.log(arr); // output: [4, 5, 6, 7]