leetcode/1365-howmany.js at main · 4pmAlgorithm/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
// Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

// Return the answer in an array.

// Input: nums = [8,1,2,2,3]
// Output: [4,0,1,1,3]
// Explanation:
// For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
// For nums[1]=1 does not exist any smaller number than it.
// For nums[2]=2 there exist one smaller number than it (1).
// For nums[3]=2 there exist one smaller number than it (1).
// For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

//#3 2022/03/15 1:12pm -
//#2 2022/03/10 #1365 howmany 5:15pm- 5:24pm
//#1 2022/03/10 #1365 howmany 4:15pm- 5:15pm


// 1. sort the arr
// 2. store the sorted num in obj w index num as val
// 3. skip the same num
// 4. return the index num for each ele of the original arr


function smallerNumbersThanCurrent(nums){
    let sorted = [...nums].sort((a,b) => a-b)

    let hash = {}, result = []

    for(let i = 0; i < sorted.length; i++){
        if(sorted[i] === sorted[i-1]) continue;
        hash[sorted[i]] = i
    }

    //console.log(hash)

    for(let i = 0; i < nums.length; i++){
        result.push(hash[nums[i]])
    }
    console.log(result)
    return result
}


smallerNumbersThanCurrent([8,1,2,2,3])


//#2 2022/03/10 #1365 howmany 5:15pm- 5:24pm
// var smallerNumbersThanCurrent = function(nums) {

//  let sorted = [...nums].sort((a,b) => a-b)
//  let hash = {}, result = [];

//   for(let i = 0; i < sorted.length; i++){
//       if(sorted[i] === sorted[i-1]) continue;
//       hash[sorted[i]] = i
//   }

//   nums.forEach((each, i) => {
//       result[i] = hash[each]
//   })

//  //  console.log(result)
//  // console.log(hash)
//   return result
// };


//#1 2022/03/10 #1365 howmany 4:15pm- 5:15pm

// function smallerNumbersThanCurrent(nums){
//  let sorted = [...nums].sort((a,b) => a-b) //concat the nums in an arr

//  let hash = {}, result = [];

//  for(let i = 0; i < sorted.length; i++){
//   console.log(sorted[i], sorted[i-1])
//   if(sorted[i] === sorted[i-1]) continue; //if the ele are same, then skip
//   hash[sorted[i]] = i
//  }


//  for(let i = 0; i < nums.length; i++){
//   result[i] = hash[nums[i]]
//  }
//  console.log(nums)
//  console.log(result)
//  console.log(hash)
// }


// var smallerNumbersThanCurrent = function(nums) {
//  let sortedArr = nums.sort((a,b) => a)

//  let hash = {};
//  let result = [];

//  nums.forEach((each, i) => {
//   hash[each] = i;
//  })

//   for(let i = 0 ; i < nums.length; i++){
//    let count = 0;
//       for(keys in hash){
//        console.log(nums[i], keys)
//        if(nums[i] >= keys){
//         console.log("++")
//         count++
//        }
//       }
//       result.push(count)
//  }

//  console.log(result)
//  return result
// };

//solution
// var smallerNumbersThanCurrent = function(nums) {
// let sortedArr = [...nums].sort((a,b)=> a-b)

// let hash = {}, res = []

// for(let i = 0; i < sortedArr.length; i++){
//  if(sortedArr[i] == sortedArr[i-1]) continue;
//     hash[sortedArr[i]] = i //the index equals the number of smaller digits in the arr
// }
// for(let i = 0; i < nums.length; i++){
//     res[i] = hash[nums[i]]
// }
// console.log(hash)
// console.log(res)
// return res
// }

// smallerNumbersThanCurrent([8,1,2,2,3])

//#1 not passing, time out
// var smallerNumbersThanCurrent = function(nums) {

//  let result = [];

//  for(let i = 0 ; i < nums.length; i++){
//       let count = 0;

//      for(let j = nums.length-1; j >=0 ; j--){
//           console.log(nums[j], nums[i])
//          if(nums[i] > nums[j]){
//              count++
//          }
//      }
//      result.push(count)
//  }
//  //console.log(result)
//  return result
// };