share my python solutions dealt with two basic conditions


  • 0
    import random
    class Solution(object):
        nums=[]
        def __init__(self, nums):
            """
            :type nums: List[int]
            :type numsSize: int
            """
            self.nums=nums
        def pick(self, target):
            """
            :type target: int
            :rtype: int
            """
            #if the nums is sorted
            if self.nums==sorted(self.nums):
                L=-1
                for i in range(len(self.nums)):
                    if self.nums[i]==target:
                        L=i
                        break
                R=L
                for j in range(len(self.nums)-1,0,-1):
                    if self.nums[j]==target:
                        R=j
                        break
                return random.randint(L,R)
            #if the nums isn't sorted
            else:
                index=[]
                for i in range(len(self.nums)):
                    if self.nums[i]==target:
                        index.append(i)
                return index[random.randint(0,len(index)-1)]
    

  • -1
    1. Most people may use dictionary to count every element's index , but this is redundancy, and the compiler will tell you " memory is limited".
    2. when dealing with sorted array, we just use two pointers: L,R to know
      target's inedx range, then return its index by random!

  • 0
    This post is deleted!

  • 0
    H

    @sa1velet I think my solution does the similar logic as your sorted part, and I sorted it firstly. But not sure why it gave me wrong answer. Any ideas? Thanks in advance.

    def __init__(self, nums):
        """
        :type nums: List[int]
        :type numsSize: int
        """
        nums.sort()
        self.nums = nums
    
    def pick(self, target):
        """
        :type target: int
        :rtype: int
        """
        last_duplicate_i = 0
        duplicate_num = 0
        for i in xrange(len(self.nums)):
            if self.nums[i] == target:
                
                last_duplicate_i = i
                duplicate_num += 1
        
        start_duplicate_i = last_duplicate_i - duplicate_num + 1
        return random.randint(start_duplicate_i, last_duplicate_i)

  • 0
    H

    @helloworld00 if sort nums directly, the original index will be changed.


  • 0
    H

    @huhu87 Yes indeed. How silly I am! Thanks!


Log in to reply
 

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