본문 바로가기

Algorithm/Leet Code

LeetCode #398 RandomPickIndex. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접

LeetCode #398 RandomPickIndex. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접


 금방 푼 것 치고 생각보다 성능이나 메모리 사용량이 잘나옴


 마지막에 벡터에서 랜덤인덱스에 해당하는 값을 반환해야 하는데, 랜덤인덱스 자체를 반환하게 해두는 실수를 해서 제출 여러번 실패함


 


LeetCode #398

Q.

 Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.


Note:

The array size can be very large. Solution that uses too much extra space will not pass the judge.



같은 정수가 있을 수 있는 정수배열이 주어지고, 타겟 넘버가 주어지면, 랜덤으로 타겟넘버의 인덱스를 반환한다. 타겟숫자는 정수배열에 무조건 있다고 볼 수 있다. (정수배열에서 타겟숫자와 같은 인덱스들 중에서 랜덤으로 하나를 뽑아낸다)


노트:

배열 사이즈가 매우 클 수 있다. 너무 많은 추가 공간을 쓰는 솔루션은 패스될 수 있다.


 


e.g. 


int[] nums = new int[] {1,2,3,3,3};


Solution solution = new Solution(nums);



// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

solution.pick(3);


// pick(1) should return 0. Since in the array only nums[0] is equal to 1.

solution.pick(1);



Process

// Process

//1. Input vector in Constructor

//2. Input target number

//3. Find target number index in the vector

//4. Pick random index

//5. Return index



// 처리과정

//1. 생성자에서 배열을 입력받는다.

//2. 타겟숫자를 입력받는다.

//3. 배열에서 타겟숫자 인덱스를 찾는다.

//4. 찾은 인덱스들에서 랜덤으로 뽑아낸다.

//5. 뽑은 인덱스 반환한다.




Code.. lemme see example code!!!

코드.. 예제코드를 보자!!!




class Solution {

private:

    vector<int> nums;

    vector<int> indexes;

    

    void getTargetIndex(int target) {

        for (int i = 0; i < nums.size(); ++i)

        {

            if (nums[i] == target)

            {

                indexes.push_back(i);

            }

        }

    }

    

public:

    Solution(vector<int> _nums) {

        nums = _nums;

    }

    

    int pick(int target) {

        

        getTargetIndex(target);

        

        return indexes[rand() % indexes.size()];

    }

};


/**

 * Your Solution object will be instantiated and called as such:

 * Solution obj = new Solution(nums);

 * int param_1 = obj.pick(target);

 */





Something else you might like...?


2019/01/16 - [Algorithm/Leet Code] - LeetCode #217 ContainsDuplicate. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접

2019/01/21 - [Algorithm/Leet Code] - LeetCode #219 ContainsDuplicate2. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접

2019/01/22 - [Algorithm/Leet Code] - LeetCode #220 ContainsDuplicate3. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접

2019/01/23 - [Algorithm/Leet Code] - LeetCode #225 ImplementStackUsingQueue. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접



2018/10/19 - [Programming/Design Pattern ] - Design pattern - Prototype (디자인패턴 - 프로토타입) / Java C++ C#



2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #60 sudoku. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive

2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #59 spiralNumbers. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive

2019/01/08 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #58 messageFromBinaryCode. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive

2019/01/07 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #57 fileNaming. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive

2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #56 digitsProduct. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar

2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #55 differentSquares. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar



2018/12/28 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 - (#9, Tell, Don't Ask)

2018/12/26 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 (1)



2018/12/26 - [Programming/Java] - JavaFx, how to show actual size image bigger than pane using scroll, 실제 크기 이미지를 스크롤바 사용하여 보여주는 방법, Java/cpp/kotlin/gui


2019/01/14 - [Programming/Java] - 자바 메모리 누수 체크/확인/고치는 방법, Memory leak check/fix in Java application, cleanCode/좋은코드/oop/객체지향



2019/01/25 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(3)

2018/12/16 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(2)

2018/12/27 - [Life/Health care] - Milk-Thistle 밀크시슬 usage/side effects/dosage/fatigue/supplement,효능/부작용/성인,소아 용법/건강/피로회복/영양제

2018/12/26 - [Life/Health care] - Selenium 셀레늄 usage/side effects/dosage 효능/부작용/성인,소아 용법