中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。求一个单链表中结点值的中位数。用js代码实现
时间: 2024-02-10 12:10:50 浏览: 33
好的,下面是用 JavaScript 实现的代码:
```javascript
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function findMedian(head) {
let n = 0,
curr = head;
while (curr) {
n++;
curr = curr.next;
}
const mid = n % 2 === 1 ? Math.floor(n / 2) + 1 : n / 2;
let slow = head,
fast = head;
for (let i = 0; i < mid - 1; i++) {
fast = fast.next;
}
if (n % 2 === 1) {
return fast.val;
} else {
return (slow.val + fast.next.val) / 2;
}
}
```
这个实现和之前提供的 Python 代码类似,主要是遍历一遍单链表,得到链表长度,然后根据链表长度的奇偶性找到中位数结点或者中位数结点的前一个结点和后一个结点,最后计算中位数的值并返回。
相关问题
中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。求一个单链表中结点值的中位数。
好的,这是一个比较常见的算法问题,我可以给您提供一种解法。
首先,我们可以遍历一遍单链表,得到它的长度 $n$。
如果 $n$ 是奇数,那么中位数是第 $\lfloor \frac{n}{2} \rfloor + 1$ 个结点的值;
如果 $n$ 是偶数,那么中位数是第 $\frac{n}{2}$ 个结点和第 $\frac{n}{2} + 1$ 个结点的值的平均数。
具体实现过程如下:
1. 定义两个指针 `slow` 和 `fast`,从头结点开始,`slow` 每次移动一步,`fast` 每次移动两步,直到 `fast` 到达链表尾部。
2. 如果链表长度为奇数,此时 `slow` 指向的就是中位数结点;如果链表长度为偶数,此时 `slow` 和 `slow` 的下一个结点就是中位数结点。
下面是这个算法的 Python 代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_median(head: ListNode) -> float:
n = 0
curr = head
while curr:
n += 1
curr = curr.next
mid = n // 2 + 1 if n % 2 == 1 else n // 2
slow, fast = head, head
for i in range(mid - 1):
fast = fast.next
if n % 2 == 1:
return fast.val
else:
return (slow.val + fast.next.val) / 2
```
希望这个算法可以帮助到您。
输入n个有序的数据并存入某一维数组中,求该数组的中位数(中位数是指排列在有序数组中间的那个数,如果数据个数为偶数,则中位数等于中间那两个元素的平均值)。
首先,我们可以对数据进行排序,然后根据数组长度的奇偶性来确定中位数的位置。
如果数组长度为奇数,中位数的位置就是数组下标为 $\frac{n}{2}$ 的元素。
如果数组长度为偶数,中位数的位置就是数组下标为 $\frac{n}{2}-1$ 和 $\frac{n}{2}$ 的两个元素。
以下是一个示例代码实现:
```python
def find_median(arr):
arr.sort()
n = len(arr)
if n % 2 == 0:
median = (arr[n//2-1] + arr[n//2]) / 2
else:
median = arr[n//2]
return median
```
这个函数接受一个有序数组作为参数,首先对数组进行排序,然后根据数组长度的奇偶性来计算中位数的值并返回。