从数组中找出最大的和最小的数

#从数组中找出最大的和最小的数| 来源: 网络整理| 查看: 265

给定一整形数组a，要求从中找出最大的数和最小的数，并计算时间复杂度。

实现1:

遍历数组，每次取数组中一个元素，分别与当前最大值和最小值进行比较，时间复杂度O(2n)

1: void search(int a[], size_t n, int &max, int &min) 2: { 3: int i; 4: max = min = a[0]; 5: 6: for (i = 1; i < n; ++i) { 7: if (a[i] > max) 8: max = a[i]; 9: if (a[i] < min) 10: min = a[i]; 11: } 12: }

实现2:

遍历数组，每次取数组中两个元素进行比较，然后将大的与当前的最大值进行比较，小的与当前的最小值进行比较，时间复杂度O(3n/2)

1: void search(int a[], size_t n, int &max, int &min) 2: { 3: int i; 4: max = min = a[0]; 5: 6: for (i = 1; i < n/2; ++i) { 7: if (a[i*2] > a[i*2+1]) { 8: if (a[i*2] > max) 9: max = a[i*2]; 10: if (a[i*2+1] < min) 11: min = a[i*2+1]; 12: } else { 13: if (a[i*2+1] > max) 14: max = a[i*2+1]; 15: if (a[i*2] < min) 16: min = a[i*2]; 17: } 18: } 19: 20: 21: if (n%2 != 0) { 22: max = (max >= a[n-1]) ? max : a[n-1]; 23: min = (min

【本文地址】

从数组中找出最大的和最小的数

从数组中找出最大的和最小的数

今日新闻

推荐新闻