PAT A1029 TwoPointers解法

拼搏现实的明天。 2022-02-21 01:47 188阅读 0赞

**一、题目**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]  
**注意：**  
[1.It][] is guaranteed that all the integers are in the range of **long int**.  
我没想明白，题目既然强调所有整数的范围在长整型内，然而**测试数据只在int范围内**。(如果数组类型声明为long long则内存超限错误，有点坑)；

**思路**(借鉴了柳神)**：**  
意识到中位数的实质是非递减数列中**位置居中**的数，所以**从小到大数**到目标位置即可；(第二个数组是递增序列，所以可以边读边数)

**二、代码**

#include<cstdio>
    
    #define _max 200001
    int num[_max];
    
    int main() {
        int N1, N2;
        scanf("%d", &N1);
        for(int i = 0; i < N1; i++) scanf("%d", &num[i]);
        scanf("%d", &N2);
        int medianPos = (N1 + N2 + 1) / 2;
        int temp, j = 0, _count = 0;
        for(int i = 0; i < N2; i++) {
            scanf("%d", &temp);
            while(j < N1 && num[j] < temp) {
                _count++;
                if(_count == medianPos) {
                    printf("%d", num[j]);
                    return 0;
                }
                j++;
            }
            _count++;
            if(_count == medianPos) {
                printf("%d", temp);
                return 0;
            }
        }
        while(j < N1) {
            _count++;
            if(_count == medianPos) {
                printf("%d", num[j]);
                return 0;
            }
            j++;
        }
        return 0;
    }

**注意：**  
1.while(j < N1 && num\[j\] < temp)  
像这种while的方式遍历数组，常遗漏的是数组越界，所以养成习惯，判断j < N1(保证数组正常访问)。

PS: 当然也可以num\[N1\] = INF；(int的最大值)

**三、缺陷**  
代码行数少不代表程序高效，但这个代码涉及很多重复部分，显得不简洁，有没有更好的写法？

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]: /images/20220221/6d41cf19628043b3a8e131d81b030109.png
[1.It]: http://1.It