N个数(其中数可重复),求出其中第m大的数。(可写出多种想法以及其适用场景,但至少写一种你最中意的那个想法)
答题说明:该题为手动判卷,答案只要写对即可,不用严格满足字符比对。
#include<stdio.h> (737)#define STLEN 20 void main(void) { int a[STLEN]={}; int N,m,i,j; int max,temp; printf("Enter N and m value:"); scanf("%d %d",&N,&m); for(i=0;i<N;i++) { scanf("%d",&a[i]); } for(i=0;i<m;i++) //排到第m个数为止 { max=i; for(j=i+1;j<N;j++) { if(a[max]<a[j]) { max=j; //选择排序 } } temp=a[max]; a[max]=a[i]; a[i]=temp; } printf("第%d个大的数是%d\n",m,a[m-1]); }
#include <stdio.h> int main() { int arr[] = {51,21,58,63,14,45,23,54,77,84,64,31,21,85,95}; int n = sizeof(arr)/sizeof(arr[0]); int i, j, temp; int m; for(i=0; i<n; i++) { for(j=0; j<n-i-1; j++) { if(arr[j] < arr[j+1]) { temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } for(i=0; i<n; i++) { printf("%d ",arr[i]); } printf("\n"); printf("请输入m的值:"); scanf("%d",&m); printf("第%d大的数为 %d\n",m,arr[m-1]); return 0; }
#include <stdio.h> #include <stdlib.h> #include <string.h> int main() { int a[100],n,m,i,j,k,t,x,y,z; printf("输入n和m:\n"); scanf("%d%d",&n,&m); printf("输入这n个数:\n"); for(i=0;i<n;i++){ scanf("%d",&a[i]); } for(j=0;j<n;j++){ x=0; y=0; z=0; for(k=0;k<n;k++){ if(a[k]<a[j]) x++; else if(a[k]>a[j]) y++; else z++; } if(x<m&&(x+z)>=m){ printf("第m大的数是:\n%d",a[j]); break; } else if(x>=m){ for(t=j+1;t<n;t++){ if(a[t]<a[j]){ j=t-1; break; } } } else{ for(t=j+1;t<n;t++){ if(a[t]>a[j]){ j=t-1; break; } } } } }
void max_values_compare_and_repleace(int *r, int m, int v) { int i; if (r[0] >= v) { return; } r[0] = v; for (i = 0; i < m - 1; i++) { if (r[i] > r[i + 1]) { //swap r[i] = r[i + 1]; r[i + 1] = v; } } } int slove(int *arr, int size, int m) { int *r = (int *)malloc(m * sizeof(int)); int i; int max_m; memset(r, -1, m * sizeof(int)); for (i = 0; i < size; i++) { max_values_compare_and_repleace(r, m, arr[i]); } max_m = r[0]; free(r); return max_m; }
#include <stdio.h> #include <time.h> #include <stdlib.h> #include <unistd.h> int maxx(int n,int m,int *x,int p); int maxx(int n,int m,int *x,int p) { int y[1]; int t; for(int i=0;i<n-1;i++)//先全部比较一次找到最大的 再递归m-1次比较进行排序 { printf("要比较的数字:%d %d\n",x[i],x[i+1]);//永远确保x[n-1]是最大的 if(x[i]>x[i+1]) { printf("成功进入交换环节\n"); y[0]=x[i]; x[i]=x[i+1]; x[i+1]=y[0]; printf("换完之后:大的%d 小的%d\n",x[i+1],x[i]); for(t=0;t<n;t++) { printf("现在的数组是%d\n",x[t]); } } } printf("现在的数组最大的是%d\n",x[n-1]); if(m==0) { return x[n-p]; } maxx(n,m-1,x,p); } int main() { srand(time(NULL)); int n,m,p; printf("随机输入N个数 得到第M大的值\n"); scanf("%d %d",&n,&m); p=m; int x[n]; for(int i=0;i<n;i++) { x[i]= rand() % 100; usleep(1); printf("随机数:%d\n",x[i]); } printf("第%d大的数为%d\n",m,maxx(n,m,x,p)); }
#pragma warning(disable:4996) #include <stdio.h> #include <stdlib.h> #include <string.h> int main() { int N, m, i, j, count = 0; printf("输入N和m的值:"); scanf("%d %d", &N, &m); if (N < m) { printf("输入的数据不符合要求!请重新输入!"); return 0; } else { int array[1000] = { 0 }; printf("输入N个整数:"); for (i = 0; i < N; i++) { scanf("%d", &array[i]); } for (i = 0; i < N; i++) { //从大到小排序 for (j = 0; j < N - i - 1; j++) { if (array[j] < array[j + 1]) { array[j] = array[j] + array[j + 1]; array[j + 1] = array[j] - array[j + 1]; array[j] = array[j] - array[j + 1]; } } } for (i = 0; i < N; i++) { //消除相同值带来的影响 if (array[i] == array[i + 1]) { if (i < m) { count++; } } } m += count; if (N < m) { printf("输入的数据不符合要求!"); } printf("输出第m大的值:"); printf("%d", array[m - 1]); return array[m]; } }
//分治思想找第k个最大 class Solution { public: int my_sort(vector<int>& nums,int l,int k,int r)//数组有效区间的起始下标,k,结束下标 { int pivot=rand()%(r-l+1); swap(nums[pivot+l],nums[r]); //pivot元素交换到有效区间的最后 int temp = l; for(int i=l;i<r;i++) { if(nums[i]>=nums[r]) { //如果大于等于则交换到前面去 swap(nums[i],nums[temp]); temp++; } } swap(nums[temp],nums[r]); //此时temp所指向的位置,左边比nums[temp]大,右边比它小 if (temp-l==k-1) return nums[temp]; //temp-l等于temp左边(不包括temp)的个数 else if(temp-l<k-1) return my_sort(nums,temp+1,k-(temp-l+1),r); //第k大出现在temp右边 else return my_sort(nums,l,k,temp-1); //否则出现在左边 } int findKthLargest(vector<int>& nums, int k) { return my_sort(nums,0,k,nums.size()-1); } };
#include "pch.h" #include <iostream> #include <stdio.h> #define STLEN 20 using namespace std; int main(void) { int a[STLEN] = {}; int N,m, i, j; int max, temp; printf("Enter N and m value:"); scanf_s("%d %d",&N,&m); for (i = 0;i < N;i++) { scanf_s("%d",&a[i]); } for (i = 0;i < m;i++) { max = i; for (j = i + 1;j < N;j++) { if (a[max] < a[j]) { max = j;//选择排序 } } temp = a[max]; a[max] = a[i]; a[i] = temp; } printf("第%d个大的数是%d\n", m, a[m - 1]); }
/* //quick sort int compare(const void* a, const void* b) { return *(int*)a - *(int*)b } int kthmax(int* arr, int n, int m) { qsort(arr, n, sizeof(int), compare); return arr[n - m]; } */ //快速选择 void swap(int* arr, int a, int b) { int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } int Partition(int* arr, int start, int end) { int root = start; int left = start + 1; int right = end; while (left <= right) { while (left <= right && arr[left] >= arr[root]) { left++; //找到比root小的数 } while (left <= right && arr[right] <= arr[root]) { right--; //找到比root大的数 } if (left < right) { swap(arr, left++, right--); } swap(arr, root, right); return right; } } int kth_max(int* arr, int n, int m) { if (n == 0) { return NULL; } int start = 0; int end = n - 1; while (1) { int position = Partition(arr, start, end); if (position == m - 1) { return arr[m - 1]; } else if (position > m - 1) { right = position - 1; } else { left = position + 1; } } }
#include<iostream> #include<vector> #include<ctime> #include<algorithm> using namespace std; int main() { int N; cin >> N; srand(time(0)); vector<int> res; for (int i = 0; i < N; ++i) { res.push_back(rand() % 10 + 1); } sort(res.begin(), res.end()); int m; cin >> m; vector<int>::iterator iter=res.begin(); while (iter != res.end()) { if (*iter ==*(iter + 1)) res.erase(iter+1); iter++; } cout << res[res.size()-m] << endl; system("pause"); return 0; } 先对数组进行排序,然后删除重复的数据,最后根据m的大小直接就可以输出m大的数据。如有不正确或者更好的办法,请大家指教~