Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

习题1.4.8找出相等的整数对的数量好像不能用二分查找 #437

Closed
consoles opened this issue Jan 17, 2019 · 1 comment
Closed
Assignees
Milestone

Comments

@consoles
Copy link

@consoles consoles commented Jan 17, 2019

例如对于数组[1, 2, 3, 4, 1, 2, 1, 2, 1, 6]来说暴力法得到的结果是9,而基于二分搜索得到的结果却是5。我的解法是先排序,相同的元素肯定是相邻的元素,这样就可以跳出不少无效的元素:

const eqPairCount2 = nums => {
    let cnt = 0;
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length && nums[j] === nums[i]; j++) {
            cnt++;
        }
    }
    return cnt;
};

这个算法虽然比平方级别的算法快,但是好像也没有达到题目所说的线性对数级别,望大神指点迷津

@ikesnowy ikesnowy self-assigned this Jan 17, 2019
@ikesnowy ikesnowy added this to the 1.4 milestone Jan 17, 2019
@ikesnowy ikesnowy added the CONFIRMED label Jan 17, 2019
ikesnowy added a commit that referenced this issue Jan 17, 2019
@ikesnowy

This comment has been minimized.

Copy link
Owner

@ikesnowy ikesnowy commented Jan 17, 2019

@consoles
感谢你对问题的指出,你的思路是正确的,二分查找确实欠妥。
修改后的答案如下:
第一步 Array.Sort 是 O(nlogn) 的,第二步计数则是 O(n) 的,因此总的时间复杂度为 O(nlogn)。
事实上,我们只需要知道某个整数重复出现的次数,就能直接算出重复整数对的数量。
重复整数对 = 1 + 2 + 3 + ... + n-1 = n(n-1) / 2。
因此我们只需要统计每个元素的出现次数,算出对应的重复整数对数量并相加。
这个过程只需要遍历一遍数组,因为某个元素在内循环统计过之后就不需要再在外循环统计了。
内外循环可以共用一个临时变量。
修改后的方法如下:

static int CountEqualLog(int[] a)
{
    int n = a.Length;
    int count = 0;
    Array.Sort(a);
    int dup = 0; // dup = 重复元素数量-1
    for (int i = 1; i < n; i++)
    {
        while (a[i - 1] == a[i])
        {
            dup++;
            i++;
        }
        count += dup * (dup + 1) / 2;
        dup = 0;
    }
    return count;
}
ikesnowy added a commit that referenced this issue Jan 17, 2019
Try Fix Issue #437 1.4.8
@consoles consoles closed this Jan 18, 2019
@ikesnowy ikesnowy added FIXED and removed IN PROGRESS labels Jan 18, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.