C# Binary Search Solution


  • 0
    G
            public IList<int> CountSmaller(int[] nums)
            {
                helperList.Clear();
                IList<int> result = new List<int>();
                if (nums == null || nums.Length == 0)
                {
                    return result;
                }
    
                for (int i = nums.Length - 1; i >= 0; --i)
                {
                    result.Add(Helper(nums[i]));
                }
                result = result.Reverse().ToList();
                return result;
            }
    
            private List<int> helperList = new List<int>();
            private int Helper(int currNum)
            {
                int result = 0;
                if (helperList.Count == 0)
                {
                    helperList.Add(currNum);
                }
                else
                {
                    result = BinarySearch(0, helperList.Count, helperList, currNum);
                    helperList.Insert(result, currNum);
                }
    
                return result;
            }
    
            private int BinarySearch(int start, int end, IList<int> array, int target)
            {
                if (start >= end)
                {
                    return start;
                }
                int middle = start + (end - start) / 2;
                if (array[middle] >= target)
                {
                    return BinarySearch(start, middle, array, target);
                }
                else
                {
                    return BinarySearch(middle + 1, end, array, target);
                }
            }
    

Log in to reply
 

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