首页Computer-ScienceCoding-Interviews

# 面试题 53：在排序数组中查找数字

# 题目一：数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。例如，输入排序数组 {1,2,3,3,3,3,4,5}\{1,2,3,3,3,3,4,5\} 和数字 33，由于 33 在这个数组中出现了 44 次，因此输出 44。

# 思路

由于输入的数组是有序的，那么我们只需要找到目标数字第一次和最后一次出现的位置，然后即可知道目标数字出现的次数。

可以通过二分法查找目标数字的上界和下界。详细解析可以参考这个链接。

# 代码

#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& nums, int target, bool lower) {
    int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] > target || (lower && nums[mid] >= target)) {
            right = mid - 1;
            ans = mid;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}
int search(vector<int>& nums, int target) {
    int leftIdx = binarySearch(nums, target, true);
    int rightIdx = binarySearch(nums, target, false) - 1;
    if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
        return rightIdx - leftIdx + 1;
    }
    return 0;
}
# 题目二：00~n−1n-1 中缺失的数字


一个长度为 n−1n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 00~n−1n-1 之内。在范围 00~n−1n-1 内的 nn 个数字中有且只有一个数字不在该数组中，请找出这个数字。


# 思路


因为 00~n−1n-1 这些数字在数组中是排序的，因此数组中开始的一些数字与它们的下标相同。即是说 00 在下标为 00 的位置，11 在下标为 11 的位置，以此类推。如果不在数组中的那个数字记为 mm，那么所有比 mm 小的数字的下标都与它们的值相同。由于 mm 不在数组中，那么 m+1m+1 处在下标为 mm 的位置，m+2m+2 处在下标为 m+1m+1 的位置，以此类推。可以发现 mm 正好是数组中第一个数值和下标不相等的下标，因此这个问题转换成在排序数组中找出第一个值和下标不相等的元素。


可以基于二分査找的算法用如下过程查找：如果中间元素的值和下标相等，那么下一轮只需要查找右半边；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标相等，这意味着这个中间的数字正好是第一个值和下标不相等的元素，它的下标就是在数组中不存在的数字；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标不相等，这意味着下一轮只需要在左半边查找即可。


# 代码


#include <iostream>
#include <vector>
using namespace std;
int get_missing_number(vector<int> &numbers) {
    if (numbers.empty()) {
        return -1;
    }
    int left = 0;
    int right = numbers.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (numbers[mid] != mid) {
            if (mid == 0 || numbers[mid - 1] == mid - 1) {
                return mid;
            }
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (left == numbers.size()) {
        return left;
    }
    return -1;
}
# 题目三：数组中数值和下标相等的元素


假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组 {−3,−1,1,3,5}\{-3,-1,1,3,5\} 中，数字 33 和它的下标相等。


# 思路


由于数组是单调递增排序的，因此可以用二分查找算法来进行查找：假设某一步抵达数组中的第 ii 个数字，且该数字的值刚好也是 ii，那么我们就找到了一个数字和其下标相等。


如果数字的值和下标不相等，假设数字的值为 mm。


先考虑 mm 大于 ii 的情形，即数字的值大于它的下标。由于数组中的所有数字都唯一并且单调递增，那么对于任意大于 00 的 kk，位于下标 i+ki+k 的数字的值大于或等于 m+km+k。另外，因为 m>im>i，所以 m+k>i+km+k>i+k。因此，位于下标 i+ki+k 的数字的值一定大于它的下标。这意味着如果第 ii 个数字的值大于 ii，那么它右边的数字都大于对应的下标，都可以忽略。下一轮只需要从它左边的数字中査找即可。数字的值 mm 小于它的下标 ii 的情形和上面类似。它左边的所有数字的值都小于对应的下标，也可以忽略。


# 代码


#include <iostream>
#include <vector>
using namespace std;
int get_number_same_as_index(vector<int> &numbers) {
    if (numbers.empty()) {
        return -1;
    }
    int left = 0;
    int right = numbers.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (numbers[mid] == mid) {
            return mid;
        }
        if (numbers[mid] > mid) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}
# 面试题 54：二叉搜索树的第 kk 大节点


# 题目


给定一棵二叉搜索树，请找出其中第 kk 大的节点。


# 思路


如果按照中序遍历的顺序遍历一棵二叉搜索树，则遍历序列的数值是递增排序的。因此，只需要用中序遍历算法遍历一棵二叉搜索树，就可以很容易找出它的第 kk 大节点。


# 代码


#include <iostream>
struct BinaryTreeNode {
    int m_value;
    BinaryTreeNode *m_left;
    BinaryTreeNode *m_right;
};
BinaryTreeNode *get_Kth_node_core(BinaryTreeNode *root, unsigned int &k) {
    BinaryTreeNode *target = nullptr;
    if (root->m_left != nullptr) {
        target = get_Kth_node_core(root->m_left, k);
    }
    if (target == nullptr) {
        if (k == 1) {
            target = root;
        }
        k--;
    }
    if (target == nullptr && root->m_right != nullptr) {
        target = get_Kth_node_core(root->m_right, k);
    }
    return target;
}
BinaryTreeNode *get_Kth_node(BinaryTreeNode *root, unsigned int k) {
    if (root == nullptr || k == 0) {
        return nullptr;
    }
    return get_Kth_node_core(root, k);
}
# 面试题 55：二叉树的深度


# 题目一：二叉树的深度


输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。


# 思路


如果一棵树只有一个节点，那么它的深度为 11。如果根节点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加 11；同样，如果根节点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加 11。如果既有右子树又有左子树，那么该树的深度就是其左、右子树深度的较大值再加 11。


# 代码


#include <iostream>
#include <cmath>
using namespace std;
struct BinaryTreeNode {
    int m_value;
    BinaryTreeNode *m_left;
    BinaryTreeNode *m_right;
};
int depth_of_tree(BinaryTreeNode *root) {
    if (root == nullptr) {
        return 0;
    }
    int left = depth_of_tree(root->m_left);
    int right = depth_of_tree(root->m_right);
    return max(left, right) + 1;
}
# 题目二：平衡二叉树


输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左、右子树的深度相差不超过 11，那么它就是一棵平衡二叉树。


# 思路


用后序遍历的方式遍历二叉树的每个节点，那么在遍历到一个节点之前已经遍历了它的左、右子树。只要在遍历每个节点的时候记录它的深度，就可以一边遍历一边判断每个节点是不是平衡的。


# 代码


#include <iostream>
#include <cmath>
using namespace std;
struct BinaryTreeNode {
    int m_value;
    BinaryTreeNode *m_left;
    BinaryTreeNode *m_right;
};
bool is_balanced(BinaryTreeNode *root, int &depth) {
    if (root == nullptr) {
        depth = 0;
        return true;
    }
    int left, right;
    if (is_balanced(root->m_left, left) &&
        is_balanced(root->m_right, right)) {
        int diff = left - right;
        if (abs(diff) <= 1) {
            depth = max(left, right) + 1;
            return true;
        }
    }
    return false;
}
bool is_balanced(BinaryTreeNode *root) {
    int depth = 0;
    return is_balanced(root, depth);
}
# 面试题 56：数组中数字出现的次数


# 题目一：数组中只出现一次的两个数字


一个整型数组里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n)O(n)，空间复杂度是 O(1)O(1)。


# 思路


异或运算具有一个性质：任何一个数字异或它自己都等于 00。也就是说，如果从头到尾依次异或数组中的每个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些成对出现两次的数字全部在异或中抵消了。


如果能够把原数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，而其他数字都成对出现两次，那么就可以利用异或得到这个数字。


如果从头到尾依次异或数组中的每个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果，因为其他数都出现了两次，在异或中全部抵消了。由于这两个数字肯定不同，那么异或的结果一定不为 00，也就是说，在这个结果数字的二进制表示中至少有一位为 11。我们在结果数字中找到第一个为 11 的位的位置，记为第 nn 位。


现在以第 nn 位是否为 11 为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第 nn 位都是 11，而第二个子数组中每个数字的第 nn 位都是 00。两个相同的数字的任意一位都是相同的，因此它们必定分在同一个数组中。每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。之后便可以通过异或运算的方式得到只出现一次的数字。


# 代码


#include <iostream>
#include <vector>
using namespace std;
bool is_bit_one(int num, unsigned int index_bit) {
    num = num >> index_bit;
    return (num & 1);
}
unsigned int find_first_bit_one(int num) {
    int index_bit = 0;
    while (((num & 1) == 0) && (index_bit < 8 * sizeof(int))) {
        num = num >> 1;
        ++index_bit;
    }
    return index_bit;
}
vector<int> find_number_appear_once(vector<int> &data) {
    vector<int> ans;
    if (data.empty()) {
        return ans;
    }
    int result_XOR = 0;
    for (int i = 0; i < data.size(); ++i) {
        result_XOR ^= data[i];
    }
    unsigned int index_of_one = find_first_bit_one(result_XOR);
    ans.push_back(0);
    ans.push_back(0);
    for (int j = 0; j < data.size(); ++j) {
        if (is_bit_one(data[j], index_of_one)) {
            ans[0] ^= data[j];
        } else {
            ans[1] ^= data[j];
        }
    }
    return ans;
}
# 题目二：数组中唯一只出现一次的数字


在一个数组中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。


# 思路


如果数组中的数字除一个只出现一次之外，其他数字都出现了两次。我们可以用异或位运算解决这个简化的问题。


尽管这里不能应用异或运算，还是可以沿用位运算的思路。如果一个数字出现三次，那么它的二进制表示的每一位（00 或者11）也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加

起来，那么每一位的和都能被 33 整除。


如果某一位的和能被 33 整除，那么那个只出现一次的数字二进制表示中对应的那一位是 00；否则就是 11。


# 代码


#include <iostream>
#include <vector>
using namespace std;
int find_number_appearing_once(vector<int> &numbers) {
    if (numbers.empty()) {
        throw "Invalid input.";
    }
    int bit_sum[32] = {0};
    for (int i = 0; i < numbers.size(); ++i) {
        int bit_mask = 1;
        for (int j = 31; j >= 0; --j) {
            int bit = numbers[i] & bit_mask;
            if (bit != 0) {
                bit_sum[j] += 1;
            }
            bit_mask = bit_mask << 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < 32; ++i) {
        ans = ans << 1;
        ans += bit_sum[i] % 3;
    }
    return ans;
}
# 面试题 57：和为 ss 的数字


# 题目一：和为 ss 的两个数字


输入一个递增排序的数组和一个数字 ss 在数组中査找两个数，使得它们的和正好是 ss。如果有多对数字的和等于 ss，则输出任意一对即可。


# 思路


由于数组是有序的，使用双指针法， left  和  right  一开始分别指向最小和最大的数字。如果当前  left  和  right  指向的数字之和大于 ss，则左移  right ；如果和小于 ss，则右移  left ；如果和等于 ss，则找到这样的一组数；如果  left  和  right  指向了相同的数字，那么说明数组中不存在这样的一组数。


# 代码


#include <iostream>
#include <vector>
using namespace std;
vector<int> find_numbers_with_sum(vector<int> &data, int target) {
    vector<int> ans;
    if (data.empty()) {
        return ans;
    }
    int left = 0, right = data.size() - 1;
    while (left < right) {
        long long cur_sum = data[left] + data[right];
        if (cur_sum == target) {
            ans.push_back(data[left]);
            ans.push_back(data[right]);
            break;
        } else if (cur_sum > target) {
            --right;
        } else {
            ++left;
        }
    }
    return ans;
}
# 题目二：和为 ss 的连续正数序列


输入一个正数 ss，打印出所有和为 ss 的连续正数序列（至少含有两个数)。


# 思路


用两个数  small  和  large  分别表示序列的最小值和最大值。首先把  small  初始化为 11， large  初始化为 22。如果从  small  到  large  的序列的和大于 ss，则可以从序列中去掉较小的值，也就是增大  small  的值。如果从  small  到  large  的序列的和小于 ss，则可以增大 large ，让这个序列包含更多的数字。因为这个序列至少要有两个数字，我们一直增加  small  到 (1+s)/2(1+s)/2 为止。


# 代码


#include <iostream>
using namespace std;
void print(int small, int large) {
    for (int i = small; i <= large; ++i) {
        cout << i << endl;
    }
}
void find_continuous_sequence_with_sum(int sum) {
    if (sum < 3) {
        return;
    }
    int small = 1;
    int large = 2;
    int mid = (1 + sum) / 2;
    int cur_sum = small + large;
    while (small < mid) {
        if (cur_sum == sum) {
            print(small, large);
        }
        while (cur_sum > sum && small < mid) {
            cur_sum -= small;
            ++small;
            if (cur_sum == sum) {
                print(small, large);
            }
        }
        ++large;
        cur_sum += large;
    }
}