Time limit: 500ms
Memory limit: 256mb
Description:
In this exercise, you are required to maintain an array of sorted integers in non-descending order and support the following operations.
1. Insert an integer
2. Delete an integer
3. Check whether an integer exists
4. Update one matching integer
5. Update all matching integers in a range (exclusive)
6. Check whether an integer appears at least twice
You can assume that there are 100 integers at most, so an array A[100] is enough to store all the integers (i.e. length A <= 100). What’s more, all the integers of A[] are not distinct, which means that A[0] <= A[1] <= … <= A[n-1].
Then the program performs Insert, Delete, Update and Print operations. The user will be prompted to input the integers for insertion, deletion, update, and check.
The code template has been provided. Your task is to complete the following functions.
int Insert(int value, int A[], int n);
Insert one value into A[] of length n and return the new length. After insertion, A[] should still be in non-descending order.
Example:
Insert 1 to [1,1,3,4,7,8] with length n = 6
Array then becomes: [1,1,1,3,4,7,8], the function returns new length n’ = 7
int Delete(int value, int A[], int n);
Delete one integer from A[] of length n and return the new length. You could assume that the value exists in A[] before deletion. After deletion, A[] should still be in non-descending order.
Example:
delete 4 from [1,1,1,3,4,7,8] with length n = 7
Array then becomes: [1,1,1,3,7,8], the function returns new length n’ = 6
int Exist(int value, int A[], int n)
Check whether a value exists in the array A[]. If exist, return 1, if not, return 0.
Example
Check whether [1,1,1,3,7,8] exists 3
The function will return 1 as 3 exists.
Check whether [1,1,1,3,7,8] exists 5
The function will return 0 as 5 does not exist.
int Update_one(int old_value, int new_value, int A[], int n);
Update one old_value to new_value in A[] of length n and return the new length. After the update, A[] should still be in non-descending order.
Example:
Update one 1 in [1,1,1,3,7,8] to 2
Array then becomes: [1,1,2,3,7,8] (i.e. only one 1 becomes 2), the function returns length n’ = 6
Tips: You may use Exist(), Insert() and Delete() to implement the Update() and do not forget to update n after insertion and deletion.
int Update_all(int old_value_min, int old_value_max, int new_value, int A[], int n);
Update all matching integers in a range (exclusive) from old_value_min to old_value_max to new_value in A[] of length n and return the new length. After the update, A[] should still be in non-descending order.
Example:
Given old_value_min = 2, old_value_max = 9, new_value = 7, and array [1,1,2,3,7,8]. Update all integers in the array with values less then 9 (< 9) and greater than 2 (> 2) to 7
Array then becomes: [1,1,2,7,7,7] (i.e. all 3,7,8 will become 7s as they are in range (exclusive) 2 to 9), the function returns length n’ = 6
int hasDuplicate(int A[], int n)
Check whether there exists any integer appears at least twice in the array A[]. If exist, return 1, if not, return 0.
Example:
Check whether [1,1,2,7,7,7] exists any integer appears at least twice
The function will return 1 as both 1 and 7 appears at least twice.
Check whether [1,2,3,4,5,6] exists any integer appears at least twice
The function will return 0 as all integers appears once only
Sample input:
5
1 3 2 5 3
4
1
2 8
2 4 1
Sample output:
1
1 1 4 5 8
-------------------------Copy the following code, complete it and submit-------------------------
#include <stdio.h>
void Print(int A[], int n)
{
// print A[0], A[1], ..., A[n-1] in one line, every two integers are separated by a space
for(int i=0; i<n; i++)
printf("%d ", A[i]);
printf("\n");
}
int Insert(int value, int A[], int n)
{
// insert value into A[], return new length n
}
int Delete(int value, int A[], int n)
{
// delete value from A[], return new length n
}
int Exist(int value, int A[], int n){
// check whether a value exists in array A[]
}
int Update_one(int old_value, int new_value, int A[], int n)
{
// change old_value to new_value, return new length n
}
int Update_all(int old_value_min, int old_value_max, int new_value, int A[], int n)
{
// change old_value in range (exclusive) from old_value_min to old_value_max to new_value, return new length n
}
int hasDuplicate(int value, int A[], int n){
// check if any value appears at least twice in array A[]
}
int main()
{
int A[100];
int n; // the number of integers in A
int value, value_min, value_max, new_value;
// Array initialization
// How many integers in array initially
scanf("%d", &n);
// What are the integers
int temp = 0;
for(int i=0; i<n; i++){
scanf("%d", &value);
temp = Insert(value, A, temp);
}
// Input a value for insertion
scanf("%d", &value);
n = Insert(value, A, n);
// Input a value for deletion
scanf("%d", &value);
n = Delete(value, A, n);
// Input the old and new values for update(one)
scanf("%d%d", &value, &new_value);
n = Update_one(value, new_value, A, n);
// Input the min old value, max olf value and new value for update(all)
scanf("%d%d%d", &value_min, &value_max, &new_value);
n = Update_all(value_min, value_max, new_value, A, n);
// Check if any value appears at least twice
printf("%d\n", hasDuplicate(A, n));
// print current array
Print(A, n);
return 0;
}
-------------------------------------------End of Code-------------------------------------------