今日头条春招第一次笔试题(一)

有幸参加了今日头条的笔试题目。这是我参加过的最难的一次笔试题目了。

第一题

题目描述

• 在n个元素的数组中，找到差值为k的数字对去重后的个数。

输入描述

• 第一行：n和k，n表示数字的个数，k表示差值。
• 第二行：n个正整数。

输出描述

• 差值为k的数字对去重后的个数

想到的解法

step 1. 排序
step 2. 遍历一遍排序后的数组. 对遍历的当前值a[i], 二分查找数组中是否存在值a[i] + k.

备注: 当时我没有用这种想法,而用了一种比这个麻烦的想法,导致accept rate只有30%. 但个人感觉这种算法也达不到AC的要求, 复杂度为$O(nlogn)$. 或许有更简单的算法, 复杂度为$O(n)$.

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool binary_find(vector<int> * arr, int front, int behind, int target)
{
    while(front <= behind)
    {
        int mid = (front + behind) / 2;
        if((*arr)[mid] < target)
        {
            front = mid + 1;
        }
        if((*arr)[mid] > target)
        {
            behind = mid - 1;
        }
        if((*arr)[mid] == target)
            return true;
    }
    return false;
}

int main() {
    int n;
    int k;
    vector<int> array;
    cin >> n >> k;

    //异常输入直接返回.
    if(n == 0)
    {
        cout << 0;
        return 1;
    }

    for(int i =0; i < n; i++)
    {
        int temp = 0;
        cin >> temp;
        array.push_back(temp);
    }

    //对数组进行排序, 用stl标准库中的sort函数
    sort(array.begin(), array.end());

    //遍历数组,对排序数组才用二分查找
    //为了不会出现数字对重复计数的情况, 因此记录当前的所遍历的数组的值.
    //然后直接遍历数组中与该值不相等的数.

    int now_value = array[0];
    int couple_num = 0;
    if(binary_find(&array, 1, n - 1, array[0] + k))
        couple_num += 1;
    for(int i =1; i < n; i++)
    {
        if(array[i] == now_value)
        {
            continue;
        }
        else
        {
            now_value = array[i];
            if(binary_find(&array, i + 1, n - 1, array[i] + k))
            {
                couple_num += 1;
            }
        }
    }

    cout << couple_num;

    return 0;
}