Shorter C# solution with build-in BinarySearch()


  • 0
    L

    I wrote a C# solution with build-in BinarySearch function. Since I used while loop (handle the duplicated elements)and List.Insert, both of them cost O(n), the complexity totally is O(n^2). So it is not a good solution, but short and easy to understand. Of course, it is passed, and beat almost 50%.

        int[] lintResult = new int[nums.Length];
        List<int> llistSorted = new List<int>();
    
        for (int i = nums.Length - 1; i >= 0; --i) {
            int lintPos = llistSorted.BinarySearch(nums[i]);
            if (lintPos >= 0) {
                while (lintPos > 0 && llistSorted[lintPos] == llistSorted[lintPos - 1]) {
                    lintPos--;
                }
                lintResult[i] = lintPos ;
            } else {
                lintPos = ~lintPos;
                lintResult[i] = lintPos;
            }
            llistSorted.Insert(lintPos, nums[i]);
        }
        return lintResult.ToList<int>();

Log in to reply
 

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