15th largest value of data flow

15  The second of data flow K Big numbers

author : Turbo The time limit : 1S chapter :  curriculum design

Problem description :

Design a data stream to find the k Classes of large elements （class）. Note that it's the... After the order k Big element , Not the first k A different element .

Please implement KthLargest class ：

    KthLargest(int k, int[] nums) Use integers k And integer stream nums Initialize object .

    int add(int val) take val Insert data stream nums after , Returns the current data stream at k Big elements .

Example ：

Input ：

3 4

4 5 8 2

add 3

add 5

add 10

add 9

add 4

Output ：

4

5

5

8

8

explain ：

KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);

kthLargest.add(3);   // return 4

kthLargest.add(5);   // return 5

kthLargest.add(10);  // return 5

kthLargest.add(9);   // return 8

kthLargest.add(4);   // return 8

Enter description :

Enter several lines ：

Enter two integers on the first line k and n,k In the representative question k,n Represents the nums Length of array .

Second line input n An integer represents the array used to initialize the object nums The elements of .

Enter the following lines add Instructions , Every add Followed by an integer to indicate val.

Tips ：

    1 <= k <= 10^4

    0 <= n <= 10^4

    -10^4 <= nums[i] <= 10^4

    -10^4 <= val <= 10^4

     Call at most add Method 10^4 Time

     Topic data assurance , In search of k Large element time , There are at least k Elements

The output shows that :

Output several lines , One integer per row , by add The return value of the instruction .

Input example :

2 4
3 5 7 6
add 5
add 4
add 8

Output example :

6
6
7
 

This code comes from our group CC classmate We must express our gratitude

、

#include<iostream>
#include<algorithm>
using namespace std;
class KthLargest
{
    int k;
    int* arr;
    int size;
public:
    KthLargest();

    KthLargest(int k, int nums[], int n);

    KthLargest(const KthLargest& K);

    KthLargest operator=(const KthLargest& K);

    ~KthLargest();

    int add(int val);
};

KthLargest::KthLargest()
{
    k = 0;
    arr = new int[100001];
    size = 0;
}
KthLargest::KthLargest(int k, int nums[], int n)
{
    this->k = k;
    arr = new int[100001];
    size = n;
    for (int i = 0; i < size; i++)
    {
        arr[i] = nums[i];
    }
}

KthLargest::KthLargest(const KthLargest& K)
{
    k = K.k;
    arr = new int[100001];
    size = K.size;
    for (int i = 0; i < size; i++)
    {
        arr[i] = K.arr[i];
    }
}

KthLargest KthLargest::operator=(const KthLargest& K)
{
    k = K.k;
    arr = new int[100001];
    size = K.size;
    for (int i = 0; i < size; i++)
    {
        arr[i] = K.arr[i];
    }
    return *this;
}

KthLargest::~KthLargest()
{
    delete[]arr;
}


int KthLargest::add(int val)
{
    int i;
    for (i = 0; i < size; i++)
    {
        if (val < arr[i])
            break;
    }
    for (int j = size; j > i; j--)
    {
        arr[j] = arr[j - 1];
    }
    arr[i] = val; size++;
    return arr[size - k];
}

int nums[10005];

int main()
{
    int k, n, i, val, theK; cin >> k >> n;
    for (i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    sort(nums, nums + n);
    string str;
    KthLargest MyK(k, nums, n);
    cin.get();
    while (cin >> str)
    {
        cin >> val;
        cin.get();
        theK = MyK.add(val);
        cout << theK << endl;
    }
    return 0;
}

  Code 2

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int x,int y)
{
	return x > y;
}
struct student
{
	int k;
	int num[100001] = {0};
	
	
	student(int k, int nums[],int n)
	{
		this->k = k;
		for (int i = 0; i < n; i++)
		{
			num[i] = nums[i];
		}
		
	}
	int add(int val,int n)
	{
		num[n] = val;
		n++;
		sort(num, num + n, cmp);
		return num[k];

	}

};

int n;

int main()
{
	int k = 0;
	cin >> k >> n;
	int arr[100001] = {0};
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	student shit(k,arr,n);
	string temp;
	for (; cin >> temp;)
	{
		if (temp == "add")
		{

			int vital=0;
			cin >> vital;
			int temp1=shit.add(vital,n);
			cout << temp1+1 << endl;

		}
	}
	return 0;
}