C solution using sets 13ms


  • 0
    V
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    
    // can be redifined for any item
    typedef int item;
    
    typedef struct set 
    { 
    	int size; 
    	item * elements; // pointer to item array allocated later
    } set;
     
    set * make_set(item arr[], int size);
    bool is_set_empty(set * st);
    bool is_member(set * st, item itm);
    void free_set(set * st);
    
    int * intersection(int * nums1, int nums1Size, int * nums2, int nums2Size, int * returnSize) 
    {
    	/* makes the two arrays into two sets and returns the common elements of the sets */
    	int i, j;
    	int * ret_array, ret_size;
    	set * nums1_set, * nums2_set, * smaller_set, * bigger_set;
    	
    	// create the sets
    	nums1_set = make_set(nums1, nums1Size);
    	nums2_set = make_set(nums2, nums2Size);
    	
    	// if sets are empty go home
    	if (is_set_empty(nums1_set) || is_set_empty(nums2_set))
    		return NULL;
    	
    	// find out which one is smaller and which one is bigger
    	if (nums1_set->size < nums2_set->size)
    	{
    		smaller_set = nums1_set;
    		bigger_set = nums2_set;
    	}
    	else
    	{
    		smaller_set = nums2_set;
    		bigger_set = nums1_set;
    	} 
    	// if they are equal it doesn't matter which is which
    	
    	// create the return array with the size of the smaller set
    	if ( (ret_array = malloc(smaller_set->size * sizeof(*ret_array)) ) == NULL)
    		exit(EXIT_FAILURE);
    	
    	// fill in only elements common for the two sets and count how many they are
    	for (i = ret_size = 0; i < smaller_set->size; ++i)
    		for (j = 0; j < bigger_set->size; ++j)
    			if (smaller_set->elements[i] == bigger_set->elements[j])
    			{
    				ret_array[ret_size++] = smaller_set->elements[i];
    				break;
    			}
    	
    	
    	free_set(nums1_set);
    	free_set(nums2_set);
    	
    	// return the number of common elements and a pointer to the first one
    	*returnSize = ret_size;
    	return ret_array;
    }
    	
    set * make_set(item arr[], int size)
    {
    	/* allocates memory and extracts only
    	 * elements which do not repeat */
    	int i, j;
    	bool is_in_set;
    	set * new_set;
    	
    	// go home if nothing to do
    	if (size < 1)
    		return NULL;
    	
    	if ( (new_set = malloc(sizeof(*new_set)) ) == NULL)
    		exit(EXIT_FAILURE);
    	
    	new_set->size = 0;
    	if ( (new_set->elements = malloc(size * sizeof(item)) ) == NULL)
    		exit(EXIT_FAILURE);
    	
    	// put in first element
    	new_set->elements[0] = arr[0];
    	++new_set->size;
    	
    	// get all other unique elements
    	for (i = 1; i < size; ++i)
    	{
    		is_in_set = false;
    		for (j = 0; j < new_set->size; ++j)
    		{
    			if (arr[i] == new_set->elements[j])
    			{
    				is_in_set = true;
    				break;
    			}
    		}
    		
    		if (!is_in_set)
    			new_set->elements[new_set->size++] = arr[i];
    	}
    			
    	return new_set;
    }
    
    bool is_set_empty(set * st)
    {
    	/* checks if set is empty */
    	return (st == NULL) ? true : false;
    }
    
    bool is_member(set * st, item itm)
    {
    	/* checks if the item exists in the set */
    	int i;
    	
    	for (i = 0; i < st->size; ++i)
    		if (i == st->elements[i])
    			return true;
    			
    	return false;
    }
    
    void free_set(set * st)
    {
    	/* frees set memory */
    	free(st->elements);
    	free(st);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.