题目地址：

https://www.lintcode.com/problem/median-ii/description

给定一个长

n

n

n数组

A

A

A，题目保证

n

n

n是偶数，返回一个新数组

B

B

B，使得

B

[

i

]

B[i]

B[i]是

A

A

A删去

A

[

i

]

A[i]

A[i]之后剩余数字的中位数。

开个新数组

C

C

C是数组

A

A

A的拷贝，对

C

C

C排序，则

C

[

i

]

C[i]

C[i]删去之后剩余数字的中位数，当

i

<

n

/

2

i<n/2

i<n/2的时候是

C

[

n

/

2

]

C[n/2]

C[n/2]，当

i

≥

n

/

2

i\ge n/2

i≥n/2的时候是

C

[

n

/

2

−

1

]

C[n/2-1]

C[n/2−1]。用哈希表

m

m

m存这个对应关系，key是

C

[

i

]

C[i]

C[i]，value是对应的中位数，则最后的答案

B

[

i

]

=

m

[

A

[

i

]

]

B[i]=m[A[i]]

B[i]=m[A[i]]。代码如下：

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

public class Solution {
    /**
     * @param arr: an integer array
     * @return: return the median array when delete a number
     */
    public int[] getMedian(int[] arr) {
        // write your code here
        int[] res = Arrays.copyOf(arr, arr.length);
        Arrays.sort(res);
        
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < res.length; i++) {
            if (i < res.length / 2) {
                map.put(res[i], res[res.length / 2]);
            } else {
                map.put(res[i], res[res.length / 2 - 1]);
            }
        }
    
    	// 把答案填回去
        for (int i = 0; i < res.length; i++) {
            res[i] = map.get(arr[i]);
        }
        
        return res;
    }
}

时间复杂度

O

(

n

log

⁡

n

)

O(n\log n)

O(nlogn)，空间

O

(

n

)

O(n)

O(n)。

本文地址：https://blog.csdn.net/qq_46105170/article/details/112232669