Yêu cầu:
Cho mảng các số nguyên A gồm n phần tử (n ≤ 30000) và số dương k (k ≤ n). Hãy chỉ ra số hạng lớn thứ k của mảng.
Ví dụ: Mảng A: 6 3 1 10 11 18
Nếu:
k = 1 => Kết quả: 18
k = 2 => Kết quả: 11
k = 3 => Kết quả: 10
…
Thuật toán:
Để giải quyết bài này, đầu tiên chúng ta dùng phương pháp sắp xếp mảng theo thứ tự giảm dần. Sau đó đếm từ trái sang phải sẽ tìm được số hạng lớn thứ k.
Code:
/************************************************************ * Author: VNCODING * History * 2014/11/16 first create VNCODING *************************************************************/ #include <stdio.h> #include <conio.h> #include <stdlib.h> bool find_kest_element(int A[], int n, int k, int *res); void sort_arr_in_descen(int A[], int n); void print_arr(int A[], int n); void main( void ) { int A[] = {1, -2, 5, 6, 8, 13, 4, 10, 27, 90, 32, 59, 76, 76, 77, 98, -90}; int len = sizeof(A)/sizeof(int); int k = 5; int res; sort_arr_in_descen(A, len); print_arr(A, len); if(find_kest_element(A, len, k, &res) == false) { printf("\nNot found k(th) largest element"); getch(); exit(0); } printf("\nThe %dth largest element in array is: %d", k, res); getch(); } //Find k(th) largest element. bool find_kest_element(int A[], int n, int k, int *res) { int i; int kest_pos; int temp = A[0]; if(k <= 0 || k > n) return false; for(kest_pos = 1,i = 1; i < n; i++) { if(temp > A[i]) { temp = A[i]; kest_pos++; } if(kest_pos == k) { *res = temp; return true; } } return false; } //Sort text in ascending void sort_arr_in_descen(int A[], int n) { int i, j; int tem; for(i = 0; i < n - 1; i++) for(j = i+1; j < n; j++) { if(A[i] < A[j]) { tem = A[i]; A[i] = A[j]; A[j] = tem; } } } //Display array void print_arr(int A[], int n) { int i; printf("\n============================="); for(i = 0; i < n; i++) { printf("\nA[%d] = %d", i, A[i]); } }
Kết quả:
============================= A[0] = 98 A[1] = 90 A[2] = 77 A[3] = 76 A[4] = 76 A[5] = 59 A[6] = 32 A[7] = 27 A[8] = 13 A[9] = 10 A[10] = 8 A[11] = 6 A[12] = 5 A[13] = 4 A[14] = 1 A[15] = -2 A[16] = -90 The 5th largest element in array is: 59
E thấy a làm rất hay , nhưng em nghĩ a nên com mấy dòng code lại để cho dễ học hơn ạ . em Cám ơn anh ạ .
@Tiệp, thank em đã đóng góp ý kiến.
Đúng là quá ít comment.
Cách của mình thì như này:
B1: Tìm Max mảng A
B2: Xóa tất cả các phần tử bằng phần tử Max trong mảng A
B3: Sử dụng vòng lặp for(i=1;i<k-1;i++) Xóa phần tử bằng phần tử Max
B4: Sau k-1 lần xóa phần tử Max, tìm Max của mảng A ta được kết quả cần tìm
Code của mình:
Sao copy từ notepad lên đây mà nó không tab nhỉ, mất hết tab rồi?
Hi Quang Linh,
Bạn đặt code trong tag này cho mình nhé, format được keep
anh ơi anh cho em hỏi mấy cái này anh dựa vào đâu hay tự suy nghĩ ra ạ ~~ cách làm a hay lắm a cho em hỏi với cách làm này mình xử lí đươc những bài toán nào a
5 2
4 10 9 10 9 9
cái này thì sao nhỉ
#include
#include
using namespace std;
const int N=1000111;
int a[N],b[N],n,k;
int main(){
cin>>n>>k; for(int i=1;i>a[i];
sort(a+1,a+1+n,greater()); //giam dan
int u=0;
for(int i=1;i0) cout<<b[k];
else cout<<a[1]; // all=nhau
}
#include
bạn ơi sao lại phải cho chạy từ 0 đến k-1 và gọi lại hàm xóa phần tử max ạ
// Thử cách này xem nhé
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
Arrays.toString(nums));
int index = 0;
int result = 0;
for(int i = nums.length -1; i >= 0; i–) {
index ++;
if(index == k) {
result = nums[i];
}
}
return result;
}