python经典百题之交换数组元素

题目: 输入数组，最大的与第一个元素交换，最小的与最后一个元素交换，输出数组

程序分析

我们需要实现一个程序，实现输入数组后将数组中的最大值与第一个元素交换，最小值与最后一个元素交换，然后输出数组。这可以通过遍历数组来找到最大值和最小值，并进行交换来实现。

方法一：遍历查找最大值和最小值

解题思路：

1. 遍历数组，找到数组中的最大值和最小值。
2. 将最大值与数组的第一个元素交换，将最小值与数组的最后一个元素交换。

代码：

def swap_max_and_min(arr):
    if not arr:
        return arr

    # Find the index of the maximum and minimum elements
    max_idx = arr.index(max(arr))
    min_idx = arr.index(min(arr))

    # Swap the maximum with the first element and minimum with the last element
    arr[0], arr[max_idx] = arr[max_idx], arr[0]
    arr[-1], arr[min_idx] = arr[min_idx], arr[-1]

    return arr


# Test the function
arr = [3, 1, 5, 8, 2, 4]
print("Original array:", arr)
result = swap_max_and_min(arr)
print("Array after swapping max and min:", result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

优点：

• 实现简单，易于理解。

缺点：

• 需要遍历数组两次以查找最大值和最小值，可能效率较低。

方法二：一次遍历查找并交换

解题思路：

1. 在一次遍历中，同时找到数组中的最大值、最小值以及它们的索引。
2. 将最大值与数组的第一个元素交换，将最小值与数组的最后一个元素交换。

代码：

def swap_max_and_min(arr):
    if not arr:
        return arr

    max_val = float('-inf')
    min_val = float('inf')
    max_idx = None
    min_idx = None

    # Find the maximum and minimum elements and their indices
    for i in range(len(arr)):
        if arr[i] > max_val:
            max_val = arr[i]
            max_idx = i
        if arr[i] < min_val:
            min_val = arr[i]
            min_idx = i

    # Swap the maximum with the first element and minimum with the last element
    arr[0], arr[max_idx] = arr[max_idx], arr[0]
    arr[-1], arr[min_idx] = arr[min_idx], arr[-1]

    return arr


# Test the function
arr = [3, 1, 5, 8, 2, 4]
print("Original array:", arr)
result = swap_max_and_min(arr)
print("Array after swapping max and min:", result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

优点：

• 在一次遍历中同时找到最大值和最小值，效率较高。

缺点：

• 需要额外的空间存储最大值和最小值的索引。

方法三：排序数组

解题思路：

1. 将数组排序，找到排序后的最大值和最小值。
2. 将最大值与数组的第一个元素交换，将最小值与数组的最后一个元素交换。

代码：

def swap_max_and_min(arr):
    if not arr:
        return arr

    sorted_arr = sorted(arr)
    max_val = sorted_arr[-1]
    min_val = sorted_arr[0]

    max_idx = arr.index(max_val)
    min_idx = arr.index(min_val)

    # Swap the maximum with the first element and minimum with the last element
    arr[0], arr[max_idx] = arr[max_idx], arr[0]
    arr[-1], arr[min_idx] = arr[min_idx], arr[-1]

    return arr


# Test the function
arr = [3, 1, 5, 8, 2, 4]
print("Original array:", arr)
result = swap_max_and_min(arr)
print("Array after swapping max and min:", result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

优点：

• 利用排序可以找到最大值和最小值，简单直接。

缺点：

• 排序算法的时间复杂度较高，不如直接遍历查找的方法效率高。

总结与推荐

• 推荐方法： 方法二，一次遍历查找并交换。在一次遍历中同时找到最大值和最小值，效率较高，不需要排序或多次遍历。
• 次选方法： 方法一，遍历查找最大值和最小值。实现简单，易于理解，但需要遍历数组两次以查找最大值和最小值。
• 备选方法： 方法三，排序数组。利用排序可以找到最大值和最小值，但排序算法的时间复杂度较高。

综上所述，推荐使用一次遍历查找并交换的方法（方法二）实现数组中的最大值与第一个元素交换，最小值与最后一个元素交换。