Here is my solution - Is there better to handle duplicated elements?


  • -2
    M
    class Solution {
    public:
        int findMin(vector<int> &num) {
            int len = num.size();
            if (len == 1)
                return num[0];
                
            int left = 0;
    		int right = len - 1;
            int mx = numeric_limits<int>::max();
            
    		while (left <= right)
    		{
    			int mid = left + (right-left)/2;
    			if (num[left] < num[mid])
    			{
    			    mx = min(num[left], mx);
    				left = mid + 1;
    			}
    			else if (num[left] > num[mid])
    			{
    			    mx = min(num[mid], mx);
    				right = mid - 1;
    			} else if (num[left] == num[mid])
    			{
    			    left++;
    			     mx = min(num[mid], mx);
    			}
    		}
    
    		return mx;
        }
    };

  • 0
    N

    I also submitted my answer and it was accepted. I am also not satisfied with my code. it is not compact.
    Any insight will be appreciated. I found the way better answer in submission answer. It is just third of my code. hopefully i will do better with rest of the submission

    public class DuplicateCircularSortedArray {
        public int findMin(int[] num) {
    		int length=num.length;
    		if(length==1)return num[0];
    		int index=findMin(0,length-1,num);
    		return num[index];
            
        }
        
        private int findMin(int low, int high,int[] num){
        	int index=-1;
        	if(num[low]<num[high])return low;
        	int mid=(low+high)/2;
        	if(low==high)return high;
        	if(low==mid && mid+1==high){
        		return high;
        	}else if(num[low]>num[mid] || num[high]<num[mid]){
        		low=low+1;
        	}else if(num[mid+1]<num[high]){
        		high=mid+1;
        	}else if(num[low]==num[high] && low!=high){
        		low=low+1;
        		high=high-1;
        	}
        	index=findMin(low,high,num);
        	return index;
        }

  • 0
    H

    Here is my answer. I solved it in recursive aloghtrim which is also the answer to the problem of the first step. I don't think you need to deal with the duplicate elements, If a'r] == a[n], it is the same as a[r] > a[n].

    int findMin(int * array, size_t size)
    

    {
    if(size == 1)
    return array[0];
    if(array[0] < array[size-1])
    return array[0];
    if(size == 2)
    return array[1];

    size_t middleIndex = size/2;
    
    int minOfFormerVector = findMin(array, middleIndex);
    int minOfLastVector = findMin(array+middleIndex, size-middleIndex);
    if(minOfFormerVector < minOfLastVector)
    	return minOfFormerVector;
    else
    	return minOfLastVector;
    

    }

    int findMin(vector<int> &num) {
    int * array = new int[num.size()];
    for(size_t n = 0; n < num.size(); ++n)
    array[n] = num[n];

    return findMin(array, num.size());
    }

  • 0
    S

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


  • 0
    S

    This solution lead to O(n), which is not idea, because the problem can be solved in O(n) with a simple scan.


Log in to reply
 

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