本站首页 返回顶部 关于博主

(1/500)找出和等于给定值的两个数

给定一个整型数组,数组未排序,请找出一对数,使这两个数的和等于一个给定的值。
例如,
输入:

arr = [8, 7, 2, 5, 3, 1]
sum = 10

输出:
Pair found at index 0 and 2 (8 + 2)

Pair found at index 1 and 4 (7 + 3)

 

1. 傻瓜式方法

傻瓜式方法比较粗暴,通过遍历给定数组中的所有两个数字组成的组合,只要发现一个组合的和等于期望中的数字,就返回它们。

C语言实现:

#include <stdio.h>

// Naive method to find a pair in an array with given sum
void findPair(int arr[], int n, int sum)
{
    // consider each element except last element
    for (int i = 0; i < n - 1; i++)
    {
        // start from i'th element till last element
        for (int j = i + 1; j < n; j++)
        {
            // if desired sum is found, print it and return
            if (arr[i] + arr[j] == sum)
            {
                printf("Pair found at index %d and %d", i, j);
                return;
            }
        }
    }

    // No pair with given sum exists in the array
    printf("Pair not found");
}

// main function
int main()
{
    int arr[] = { 8, 7, 2, 5, 3, 1 };
    int sum = 10;

    int n = sizeof(arr)/sizeof(arr[0]);
    findPair(arr, n, sum);
    return 0;
}

下载代码 运行代码

Java语言实现:

class FindPair
{
    // Naive method to find a pair in an array with given sum
    public static void findPair(int arr[], int sum)
    {
        // n is length of the array
        int n = arr.length;

        // consider each element except last element
        for (int i = 0; i < n - 1; i++)
        {
            // start from i'th element till last element
            for (int j = i + 1; j < n; j++)
            {
                // if desired sum is found, print it and return
                if (arr[i] + arr[j] == sum)
                {
                    System.out.println("Pair found at index " + i +
                                        " and " + j);
                    return;
                }
            }
        }

        // No pair with given sum exists in the array
        System.out.println("Pair not found");
    }

    // main function
    public static void main (String[] args)
    {
        int arr[] = { 8, 7, 2, 5, 3, 1 };
        int sum = 10;

        findPair(arr, sum);
    }
}

下载代码 运行代码

输出:
Pair found at index 0 and 2

这种解决方案的时间复杂度是 O(n2),空间复杂度是 O(1)

 

2. 使用排序复杂度为O(nlogn)的方法

这种方法的观点是,先对数组进行排序,然后通过两个索引index(高high和低low)来进行搜索。在初始状态时,这两个索引index分别指向数组的首尾(假设数组长度为n,low指向第0个元素,high指向第n-1个元素)。然后我们不断地逼近low和high的值来搜索数组arr[low...high],直到low大于或等于high。在这个过程中,我们计算arr[high]与arr[low]之和,并与给定的数字比较,如果和小于给定数字,就增加low的值,反之则减少high的值。最后,如果在数组中找到了这一对数字,返回它们即可。

C++语言实现:

#include <bits/stdc++.h>

// Function to find a pair in an array with given sum using Sorting
void findPair(int arr[], int n, int sum)
{
    // sort the array in ascending order
    std::sort(arr, arr + n);

    // maintain two indexes pointing to end-points of the array
    int low = 0;
    int high = n - 1;

    // reduce search space arr[low..high] at each iteration of the loop

    // loop till low is less than high
    while (low < high)
    {
        // sum found
        if (arr[low] + arr[high] == sum)
        {
             std::cout << "Pair found";
             return;
        }

        // increment low index if total is less than the desired sum
        // decrement high index is total is more than the sum
        (arr[low] + arr[high] < sum)? low++: high--;
    }

    // No pair with given sum exists in the array
    std::cout << "Pair not found";
}

// main function
int main()
{
    int arr[] = { 8, 7, 2, 5, 3, 1};
    int sum = 10;

    int n = sizeof(arr)/sizeof(arr[0]);
    findPair(arr, n, sum);
    return 0;
}

下载代码 运行代码

java语言实现:

import java.util.Arrays;

class FindPair
{
    // Naive method to find a pair in an array with given sum
    public static void findPair(int arr[], int sum)
    {
        // sort the array in ascending order
        Arrays.sort(arr);

        // maintain two indexes pointing to end-points of the array
        int low = 0;
        int high = arr.length - 1;

        // reduce search space arr[low..high] at each iteration of the loop

        // loop till low is less than high
        while (low < high)
        {
            // sum found
            if (arr[low] + arr[high] == sum)
            {
                System.out.println("Pair found");
                return;
            }

            // increment low index if total is less than the desired sum
            // decrement high index is total is more than the sum
            if (arr[low] + arr[high] < sum)
                low++;
            else
                high--;
        }

        // No pair with given sum exists in the array
        System.out.println("Pair not found");
    }

    // main function
    public static void main (String[] args)
    {
        int arr[] = { 8, 7, 2, 5, 3, 1 };
        int sum = 10;

        findPair(arr, sum);
    }
}

下载代码 运行代码

输出:
Pair found

这种解决方案的时间复杂度是 O(nlogn),空间复杂度是 O(1)。

 

3. 使用Map复杂度为O(n)的方法

其实,我们可以在线性的时间内解决问题,解决方案的关键在于使用map。算法就是把数组中的元素arr[i]插入到map中。在遍历数组过程中,我们需要查找sum - arr[i]是否在数组中。如果能找到,就打印出arr[i]和sum-array[i],返回。

C++语言实现:

#include <bits/stdc++.h>
using namespace std;

// Function to find a pair in an array with given sum using Hashing
void findPair(int arr[], int n, int sum)
{
    // create an empty map
    unordered_map<int, int> map;

    // do for each element
    for (int i = 0; i < n; i++)
    {
        // check if pair (arr[i], sum-arr[i]) exists

        // if difference is seen before, print the pair
        if (map.find(sum - arr[i]) != map.end())
        {
            cout << "Pair found at index " << map[sum - arr[i]] <<
                    " and " << i;
            return;
        }

        // store index of current element in the map
        map[arr[i]] = i;
    }

    // we reach here if pair is not found
    cout << "Pair not found";
}

// main function
int main()
{
    int arr[] = { 8, 7, 2, 5, 3, 1};
    int sum = 10;

    int n = sizeof(arr)/sizeof(arr[0]);
    findPair(arr, n, sum);
    return 0;
}

下载代码 运行代码

java语言实现:

import java.util.HashMap;
import java.util.Map;

class FindPair
{
    // Naive method to find a pair in an array with given sum
    public static void findPair(int arr[], int sum)
    {
        // create an empty Hash Map
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        // do for each element
        for (int i = 0; i < arr.length; i++)
        {
            // check if pair (arr[i], sum-arr[i]) exists

            // if difference is seen before, print the pair
            if (map.containsKey(sum - arr[i]))
            {
                System.out.println("Pair found at index " +
                        map.get(sum - arr[i]) + " and " + i);
                return;
            }

            // store index of current element in the map
            map.put(arr[i], i);
        }

        // No pair with given sum exists in the array
        System.out.println("Pair not found");
    }

    // main function
    public static void main (String[] args)
    {
        int arr[] = { 8, 7, 2, 5, 3, 1 };
        int sum = 10;

        findPair(arr, sum);
    }
}

下载代码 运行代码

输出:
Pair found at index 0 and 2

这种方案的时间复杂度和空间复杂度都是O(n)。

 

练习: 打印出数组中所有和等于给定值的数字对。

数据结构与算法500例

既然决定开始让自己坚持写作,那就从翻译《数据结构与算法500例》开始吧。一方面,这500个例子对巩固算法能力、扩展思维有很大的帮助;另一方面,对我而言,它难度不大,占用时间不多,容易坚持下来。

这500例的英文原文来自:500 Data Structures and Algorithms practice problems and their solutions

番茄工作法不适合程序开发

最近又有朋友在朋友圈推荐番茄工作法。作为一枚码农,说实话,我很不推荐在软件开发过程中采用番茄工作法。
软件开发是一项精神高度集中的脑力劳动。在编程过程中,需要长时间的专注,稍微地打断一下很有可能得话费很长时间进入打断之前的状态。而番茄工作法以25分钟为单位造成的后果就是刚刚进入状态很快就被打断,严重降低写代码的效率。在工作中,在家上班一天的效率很多时候比在公司上班两天的效率还高,就是因为在家干扰小,容易精力集中。
对于不必长时间专注的工作,可以使用番茄工作法。如果自身很难精力集中,或者做一些枯燥或很难让人精力集中的事情,番茄工作法倒是一个不错的选择,它能很大程度地提高效率。

吃饭与团队满意

–由吃饭想到的

吃完饭回来的时候,团队的一哥们偷偷对我说,“Frank,没想到你会拿自己的award请大家一起吃饭,太令人感动了。”
这哥们继续说,“如果PM都你这样,能处处能为我们着想就好了。”

其实,这哥们没有全面了解我请大家吃饭的原因。让大家开心,只是原因之一。
半年前,公司新成立一个重要性很高的项目组,从各个部门借调人手做这个项目,于是我从原来部门借调出来加入这个临时的项目组。
最近项目刚结束,邀请项目团队的核心成员给原来的部门做了次技术分享,然后申请了一个award,最后用这个award来请大家吃饭。

这不是工作必须的,我为什么要做这么做呢?
作为项目经理,工作目标无非是三个目标:让领导满意、让团队满意、让我自己满意。而我所做的,就是为了实现这三个目标。
怎样让领导满意呢?在这个项目里,按期保质保量完成任务,项目的直属领导满意;让团队成员向我所属的部门做技术分享,让原部门领导知道我的成绩,部门领导也满意。
怎样让团队成员满意呢?在项目过程中,从团队成员的立场思考问题,帮助大家解决问题,与此同时,以请吃饭的方式提高团队的满意度。
怎样让自己满意呢?向领导展现我的个人能力,提高在公司的曝光度,这对以后升职加薪有好处;向团队成员展现我的友好并获取大家的信任,毕竟以后大家有需要帮助的可能。

有感PMI Exam Dev Workshop

有幸参加了PMI协会在上海举办的PMI Exam Development Workshop活动。这是PMI协会第二次在中国举办此活动,上一次是2009年北京。
我第一次参加,感觉收获很多。

我们知道,PMI考试题库中的考题一直在不断地完善中,这就需要不断地淘汰旧题目,引入新题目,这次活动的目的就是补充新考题。整个活动分2个主题:评审已存在的题目和添加新的题目。

第一天下午主要是PMI协会高管的演讲。
第二天工作内容是评审以往的考题。部分考题来自题库中不计入考试分数的题目,部分来自其他PMI Exam Dev Workshop提交的题目。每个题目都会对应到项目开发周期中相应的领域(Domain)和任务(Task),无论是题干,还是选项都有很严格的要求。这种出题的方式对其他行业出考题还是很有借鉴意义的。因为签过协议,在此不方便提及更多题目相关的内容。
第三天工作内容是自己写题目。由于头一天评审过题目,所以基本上已经驾轻就熟了。大家可以参考自己以往的工作经验,项目中碰到的问题或经验,然后写出来。题目完成之后,与其他组相互评审,最后成题。

总结一下:
1.在项目管理方面有些新的感触。一方面来源于第一天PMI协会高管的演讲,另一方面,接下来两天评审题目、写题目,参考资料,讨论问题,相互交流。
2.认识了不少朋友。毕竟,扩展社交圈对个人的发展是很重要的。