Finding third smallest number in a given set of numbers with least time complexity
0
Here's a working algorithm that finds the third smallest number in a given set of numbers.
I was looking for another solutions to the given requirement with less time complexity.
Here's the working code:
Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
var x = 0;
var y = 0;
function FindThirdSmallestNumber() {
for(var i=0;i<Numbers.length;i++) {
if (Numbers[i] > Numbers[i+1]) {
x = Numbers[i];
y = Numbers[i+1];
Numbers[i] = y;
Numbers[i+1] = x;
i=-1;
} else {
//
}
}
console.log(Numbers[2]);
}
FindThirdSmallestNumber();javascript
asked Nov 21 at 1:29
CoreDo
98131018
|
show 1 more comment
0
Here's a working algorithm that finds the third smallest number in a given set of numbers.
I was looking for another solutions to the given requirement with less time complexity.
Here's the working code:
Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
var x = 0;
var y = 0;
function FindThirdSmallestNumber() {
for(var i=0;i<Numbers.length;i++) {
if (Numbers[i] > Numbers[i+1]) {
x = Numbers[i];
y = Numbers[i+1];
Numbers[i] = y;
Numbers[i+1] = x;
i=-1;
} else {
//
}
}
console.log(Numbers[2]);
}
FindThirdSmallestNumber();javascript
asked Nov 21 at 1:29
CoreDo
98131018
What do you mean by less time complexity?
– Abana Clara
Nov 21 at 1:33
1
For the general case (kth smallest) you can use a max heap with a resulting time complexity of O(n log k).
– slider
Nov 21 at 1:34
if you only need the 3rd smallest you can use 3 variables to keep track of the 3 smallest numbers and find the 3rd smallest in linear time..
– Chris Li
Nov 21 at 1:37
Numbersis not a good variable name given it's similarity to the built–in Number object. Your approach seems to be a bubble sort, which is very inefficient and may require multiple passes to fully order the array (basically you keep iterating until nothing moves). I think thei -= 1is redundant, it just means the same to values are tested again on the next iteration.
– RobG
Nov 21 at 1:41
Can you please explicitly state what the time complexity of your above algorithm is?
– slider
Nov 21 at 1:49
|
show 1 more comment
0
0
0
Here's a working algorithm that finds the third smallest number in a given set of numbers.
I was looking for another solutions to the given requirement with less time complexity.
Here's the working code:
Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
var x = 0;
var y = 0;
function FindThirdSmallestNumber() {
for(var i=0;i<Numbers.length;i++) {
if (Numbers[i] > Numbers[i+1]) {
x = Numbers[i];
y = Numbers[i+1];
Numbers[i] = y;
Numbers[i+1] = x;
i=-1;
} else {
//
}
}
console.log(Numbers[2]);
}
FindThirdSmallestNumber();javascript
asked Nov 21 at 1:29
CoreDo
98131018
Here's a working algorithm that finds the third smallest number in a given set of numbers.
I was looking for another solutions to the given requirement with less time complexity.
Here's the working code:
Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
var x = 0;
var y = 0;
function FindThirdSmallestNumber() {
for(var i=0;i<Numbers.length;i++) {
if (Numbers[i] > Numbers[i+1]) {
x = Numbers[i];
y = Numbers[i+1];
Numbers[i] = y;
Numbers[i+1] = x;
i=-1;
} else {
//
}
}
console.log(Numbers[2]);
}
FindThirdSmallestNumber();Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
var x = 0;
var y = 0;
function FindThirdSmallestNumber() {
for(var i=0;i<Numbers.length;i++) {
if (Numbers[i] > Numbers[i+1]) {
x = Numbers[i];
y = Numbers[i+1];
Numbers[i] = y;
Numbers[i+1] = x;
i=-1;
} else {
//
}
}
console.log(Numbers[2]);
}
FindThirdSmallestNumber();Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
var x = 0;
var y = 0;
function FindThirdSmallestNumber() {
for(var i=0;i<Numbers.length;i++) {
if (Numbers[i] > Numbers[i+1]) {
x = Numbers[i];
y = Numbers[i+1];
Numbers[i] = y;
Numbers[i+1] = x;
i=-1;
} else {
//
}
}
console.log(Numbers[2]);
}
FindThirdSmallestNumber();javascript
javascript
asked Nov 21 at 1:29
CoreDo
98131018
asked Nov 21 at 1:29
CoreDo
98131018
asked Nov 21 at 1:29
CoreDo
98131018
asked Nov 21 at 1:29
CoreDo
98131018
asked Nov 21 at 1:29
CoreDo
98131018
98131018
What do you mean by less time complexity?
– Abana Clara
Nov 21 at 1:33
1
For the general case (kth smallest) you can use a max heap with a resulting time complexity of O(n log k).
– slider
Nov 21 at 1:34
if you only need the 3rd smallest you can use 3 variables to keep track of the 3 smallest numbers and find the 3rd smallest in linear time..
– Chris Li
Nov 21 at 1:37
Numbersis not a good variable name given it's similarity to the built–in Number object. Your approach seems to be a bubble sort, which is very inefficient and may require multiple passes to fully order the array (basically you keep iterating until nothing moves). I think thei -= 1is redundant, it just means the same to values are tested again on the next iteration.
– RobG
Nov 21 at 1:41
Can you please explicitly state what the time complexity of your above algorithm is?
– slider
Nov 21 at 1:49
|
show 1 more comment
What do you mean by less time complexity?
– Abana Clara
Nov 21 at 1:33
1
For the general case (kth smallest) you can use a max heap with a resulting time complexity of O(n log k).
– slider
Nov 21 at 1:34
if you only need the 3rd smallest you can use 3 variables to keep track of the 3 smallest numbers and find the 3rd smallest in linear time..
– Chris Li
Nov 21 at 1:37
Numbersis not a good variable name given it's similarity to the built–in Number object. Your approach seems to be a bubble sort, which is very inefficient and may require multiple passes to fully order the array (basically you keep iterating until nothing moves). I think thei -= 1is redundant, it just means the same to values are tested again on the next iteration.
– RobG
Nov 21 at 1:41
Can you please explicitly state what the time complexity of your above algorithm is?
– slider
Nov 21 at 1:49
What do you mean by less time complexity?
– Abana Clara
Nov 21 at 1:33
What do you mean by less time complexity?
– Abana Clara
Nov 21 at 1:33
1
1
For the general case (kth smallest) you can use a max heap with a resulting time complexity of O(n log k).
– slider
Nov 21 at 1:34
For the general case (kth smallest) you can use a max heap with a resulting time complexity of O(n log k).
– slider
Nov 21 at 1:34
if you only need the 3rd smallest you can use 3 variables to keep track of the 3 smallest numbers and find the 3rd smallest in linear time..
– Chris Li
Nov 21 at 1:37
if you only need the 3rd smallest you can use 3 variables to keep track of the 3 smallest numbers and find the 3rd smallest in linear time..
– Chris Li
Nov 21 at 1:37
Numbers is not a good variable name given it's similarity to the built–in Number object. Your approach seems to be a bubble sort, which is very inefficient and may require multiple passes to fully order the array (basically you keep iterating until nothing moves). I think the i -= 1 is redundant, it just means the same to values are tested again on the next iteration.– RobG
Nov 21 at 1:41
Numbers is not a good variable name given it's similarity to the built–in Number object. Your approach seems to be a bubble sort, which is very inefficient and may require multiple passes to fully order the array (basically you keep iterating until nothing moves). I think the i -= 1 is redundant, it just means the same to values are tested again on the next iteration.– RobG
Nov 21 at 1:41
Can you please explicitly state what the time complexity of your above algorithm is?
– slider
Nov 21 at 1:49
Can you please explicitly state what the time complexity of your above algorithm is?
– slider
Nov 21 at 1:49
|
show 1 more comment
5 Answers
5
active
oldest
votes
1
Not sure if this is any faster but it's shorter:
//Use a custom sort function and pass it to the .sort() method
Numbers = Numbers.sort(function(x, y){ return x - y; });
if(Numbers.length > 2){
//At this point, the 3rd item in the array should be the 3rd lowest
console.log(Numbers[2]);
}else {
console.log("There are not 3 numbers in the array.");
}
answered Nov 21 at 1:38
Ryan Wilson
3,4641518
I think the OP wants to do the sort manually (or apply some other algorithm), not rely in the built–in sort (which was my first thought too).
– RobG
Nov 21 at 1:42
@RobG Oh. Sorry. CoreDo, Is this not what you were looking for? If so, I can remove it.
– Ryan Wilson
Nov 21 at 1:43
Optimizing programmer time over program execution time is almost always the right call, unless you can prove otherwise using a profiler. That’s why I like this answer.
– VorpalSword
Nov 21 at 1:43
No need to remove it. The more the merrier. Plus, it really addresses the problem to some degree.
– Abana Clara
Nov 21 at 1:45
1
@VorpalSword—I disagree with that as a generalisation. Programmer time is a one–off, execution time is every single time code is executed, which might be millions of times per day. It doesn't take long to recover an extra few minutes, or even hours, of programmer time if your client is the one also paying for the users' time. ;-)
– RobG
Nov 21 at 2:20
|
show 2 more comments
1
One option would be to have a separate sorted array of the three smallest numbers so far. Whenever you run across a number smaller than the 3rd smallest (the last in the sorted array), reassign that 3rd index to the new number, and sort it again:
const numbers = [3, 2, 55, -10, -55, 5, 3, 2, 1, -5, 33, 9, -1, 4, 5];
const sortNumeric = (a, b) => a - b;
function FindThirdSmallestNumber(input) {
const [smallestSoFar, numbers] = [input.slice(0, 3), input.slice(3)];
smallestSoFar.sort(sortNumeric);
numbers.forEach((num) => {
if (num < smallestSoFar[2]) {
smallestSoFar[2] = num;
smallestSoFar.sort(sortNumeric);
}
});
return smallestSoFar[2];
}
console.log(FindThirdSmallestNumber(numbers));Note that implementations that sort the whole array (as other answers do) is O(N log N), while sorting here is only ever done on an array of size 3, which is significantly less complex (O(N log 3) I think, which is equivalent to O(N))
answered Nov 21 at 1:40
CertainPerformance
74.4k143659
add a comment |
1
This one should be a lot simpler. Also not sure about this being any faster but in the most simple/obvious cases less code = better performance.
I just sort the array ascending and get the value based on index. So with this code you can get any place; lowest, second lowest, third lowest, etc as long as your index does not go out of range.
const input = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function getLowestByRank(data, rank) {
data.sort(function(a, b){ return a - b });
return data[rank - 1];
}
console.log(getLowestByRank(input, 3))
console.log(getLowestByRank(input, 2))
console.log(getLowestByRank(input, 4))
answered Nov 21 at 1:37
Abana Clara
1,511819
add a comment |
0
You can use Math.min function to determine the minimum until you find your X smallest number:
Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function FindSmallestNumber(arr, limit) {
var min = '';
for(var counter = 1; counter <= limit; counter ++) {
min = Math.min.apply(Math, arr);
arr.splice(arr.indexOf(min), 1);
}
console.log(min);
}
FindSmallestNumber(Numbers, 3); //3rd smallest number
answered Nov 21 at 1:42
Mojo Allmighty
645316
add a comment |
0
I think sorting the array is likely the fastest method, but perhaps you want avoid the built–in sort. An alternative is as Chris Li suggests: iterate over the values and just keep the 3 lowest, then return the highest of the three.
I assumed you want to avoid built-in methods, so this only uses some basic array methods and does everything else manually.
// Avoid Math.max
function getMax(arr) {
var max = -Infinity;
for (var i=0, iLen=arr.length; i<iLen; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
// If data.length < 4, just returns largest value
// Iterates over data once
function get3rdSmallest(data) {
// Helper to insert value in order
// Expects arr to be length 3 or smaller
function insertNum(arr, num) {
if (!arr.length || num < arr[0]) {
nums.unshift(num);
} else if (num > arr[arr.length-1]) {
arr.push(num);
} else {
arr[2] = arr[1];
arr[1] = num;
}
}
var num, nums = ;
if (data.length < 4) {
return getMax(data);
}
for (var i=0, iLen=data.length; i<iLen; i++) {
num = data[i];
// Insert first 3 values sorted
if (nums.length < 3) {
insertNum(nums, num);
// If num is smaller than largest value in nums,
// remove move largest and insert num
} else if (num < nums[2]){
nums.splice(-1);
insertNum(nums, num);
}
}
// Return highest (last) value in nums
return nums[2];
}
var data = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
console.log(get3rdSmallest([-4,-22])); // -4
console.log(get3rdSmallest([4,0,1,7,6])); // 4
console.log(get3rdSmallest(data)); // -5answered Nov 21 at 2:16
RobG
96.8k19103145
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53404068%2ffinding-third-smallest-number-in-a-given-set-of-numbers-with-least-time-complexi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
1
Not sure if this is any faster but it's shorter:
//Use a custom sort function and pass it to the .sort() method
Numbers = Numbers.sort(function(x, y){ return x - y; });
if(Numbers.length > 2){
//At this point, the 3rd item in the array should be the 3rd lowest
console.log(Numbers[2]);
}else {
console.log("There are not 3 numbers in the array.");
}
answered Nov 21 at 1:38
Ryan Wilson
3,4641518
I think the OP wants to do the sort manually (or apply some other algorithm), not rely in the built–in sort (which was my first thought too).
– RobG
Nov 21 at 1:42
@RobG Oh. Sorry. CoreDo, Is this not what you were looking for? If so, I can remove it.
– Ryan Wilson
Nov 21 at 1:43
Optimizing programmer time over program execution time is almost always the right call, unless you can prove otherwise using a profiler. That’s why I like this answer.
– VorpalSword
Nov 21 at 1:43
No need to remove it. The more the merrier. Plus, it really addresses the problem to some degree.
– Abana Clara
Nov 21 at 1:45
1
@VorpalSword—I disagree with that as a generalisation. Programmer time is a one–off, execution time is every single time code is executed, which might be millions of times per day. It doesn't take long to recover an extra few minutes, or even hours, of programmer time if your client is the one also paying for the users' time. ;-)
– RobG
Nov 21 at 2:20
|
show 2 more comments
1
Not sure if this is any faster but it's shorter:
//Use a custom sort function and pass it to the .sort() method
Numbers = Numbers.sort(function(x, y){ return x - y; });
if(Numbers.length > 2){
//At this point, the 3rd item in the array should be the 3rd lowest
console.log(Numbers[2]);
}else {
console.log("There are not 3 numbers in the array.");
}
answered Nov 21 at 1:38
Ryan Wilson
3,4641518
I think the OP wants to do the sort manually (or apply some other algorithm), not rely in the built–in sort (which was my first thought too).
– RobG
Nov 21 at 1:42
@RobG Oh. Sorry. CoreDo, Is this not what you were looking for? If so, I can remove it.
– Ryan Wilson
Nov 21 at 1:43
Optimizing programmer time over program execution time is almost always the right call, unless you can prove otherwise using a profiler. That’s why I like this answer.
– VorpalSword
Nov 21 at 1:43
No need to remove it. The more the merrier. Plus, it really addresses the problem to some degree.
– Abana Clara
Nov 21 at 1:45
1
@VorpalSword—I disagree with that as a generalisation. Programmer time is a one–off, execution time is every single time code is executed, which might be millions of times per day. It doesn't take long to recover an extra few minutes, or even hours, of programmer time if your client is the one also paying for the users' time. ;-)
– RobG
Nov 21 at 2:20
|
show 2 more comments
1
1
1
Not sure if this is any faster but it's shorter:
//Use a custom sort function and pass it to the .sort() method
Numbers = Numbers.sort(function(x, y){ return x - y; });
if(Numbers.length > 2){
//At this point, the 3rd item in the array should be the 3rd lowest
console.log(Numbers[2]);
}else {
console.log("There are not 3 numbers in the array.");
}
answered Nov 21 at 1:38
Ryan Wilson
3,4641518
Not sure if this is any faster but it's shorter:
//Use a custom sort function and pass it to the .sort() method
Numbers = Numbers.sort(function(x, y){ return x - y; });
if(Numbers.length > 2){
//At this point, the 3rd item in the array should be the 3rd lowest
console.log(Numbers[2]);
}else {
console.log("There are not 3 numbers in the array.");
}
answered Nov 21 at 1:38
Ryan Wilson
3,4641518
answered Nov 21 at 1:38
Ryan Wilson
3,4641518
answered Nov 21 at 1:38
Ryan Wilson
3,4641518
answered Nov 21 at 1:38
Ryan Wilson
3,4641518
3,4641518
I think the OP wants to do the sort manually (or apply some other algorithm), not rely in the built–in sort (which was my first thought too).
– RobG
Nov 21 at 1:42
@RobG Oh. Sorry. CoreDo, Is this not what you were looking for? If so, I can remove it.
– Ryan Wilson
Nov 21 at 1:43
Optimizing programmer time over program execution time is almost always the right call, unless you can prove otherwise using a profiler. That’s why I like this answer.
– VorpalSword
Nov 21 at 1:43
No need to remove it. The more the merrier. Plus, it really addresses the problem to some degree.
– Abana Clara
Nov 21 at 1:45
1
@VorpalSword—I disagree with that as a generalisation. Programmer time is a one–off, execution time is every single time code is executed, which might be millions of times per day. It doesn't take long to recover an extra few minutes, or even hours, of programmer time if your client is the one also paying for the users' time. ;-)
– RobG
Nov 21 at 2:20
|
show 2 more comments
I think the OP wants to do the sort manually (or apply some other algorithm), not rely in the built–in sort (which was my first thought too).
– RobG
Nov 21 at 1:42
@RobG Oh. Sorry. CoreDo, Is this not what you were looking for? If so, I can remove it.
– Ryan Wilson
Nov 21 at 1:43
Optimizing programmer time over program execution time is almost always the right call, unless you can prove otherwise using a profiler. That’s why I like this answer.
– VorpalSword
Nov 21 at 1:43
No need to remove it. The more the merrier. Plus, it really addresses the problem to some degree.
– Abana Clara
Nov 21 at 1:45
1
@VorpalSword—I disagree with that as a generalisation. Programmer time is a one–off, execution time is every single time code is executed, which might be millions of times per day. It doesn't take long to recover an extra few minutes, or even hours, of programmer time if your client is the one also paying for the users' time. ;-)
– RobG
Nov 21 at 2:20
I think the OP wants to do the sort manually (or apply some other algorithm), not rely in the built–in sort (which was my first thought too).
– RobG
Nov 21 at 1:42
I think the OP wants to do the sort manually (or apply some other algorithm), not rely in the built–in sort (which was my first thought too).
– RobG
Nov 21 at 1:42
@RobG Oh. Sorry. CoreDo, Is this not what you were looking for? If so, I can remove it.
– Ryan Wilson
Nov 21 at 1:43
@RobG Oh. Sorry. CoreDo, Is this not what you were looking for? If so, I can remove it.
– Ryan Wilson
Nov 21 at 1:43
Optimizing programmer time over program execution time is almost always the right call, unless you can prove otherwise using a profiler. That’s why I like this answer.
– VorpalSword
Nov 21 at 1:43
Optimizing programmer time over program execution time is almost always the right call, unless you can prove otherwise using a profiler. That’s why I like this answer.
– VorpalSword
Nov 21 at 1:43
No need to remove it. The more the merrier. Plus, it really addresses the problem to some degree.
– Abana Clara
Nov 21 at 1:45
No need to remove it. The more the merrier. Plus, it really addresses the problem to some degree.
– Abana Clara
Nov 21 at 1:45
1
1
@VorpalSword—I disagree with that as a generalisation. Programmer time is a one–off, execution time is every single time code is executed, which might be millions of times per day. It doesn't take long to recover an extra few minutes, or even hours, of programmer time if your client is the one also paying for the users' time. ;-)
– RobG
Nov 21 at 2:20
@VorpalSword—I disagree with that as a generalisation. Programmer time is a one–off, execution time is every single time code is executed, which might be millions of times per day. It doesn't take long to recover an extra few minutes, or even hours, of programmer time if your client is the one also paying for the users' time. ;-)
– RobG
Nov 21 at 2:20
|
show 2 more comments
1
One option would be to have a separate sorted array of the three smallest numbers so far. Whenever you run across a number smaller than the 3rd smallest (the last in the sorted array), reassign that 3rd index to the new number, and sort it again:
const numbers = [3, 2, 55, -10, -55, 5, 3, 2, 1, -5, 33, 9, -1, 4, 5];
const sortNumeric = (a, b) => a - b;
function FindThirdSmallestNumber(input) {
const [smallestSoFar, numbers] = [input.slice(0, 3), input.slice(3)];
smallestSoFar.sort(sortNumeric);
numbers.forEach((num) => {
if (num < smallestSoFar[2]) {
smallestSoFar[2] = num;
smallestSoFar.sort(sortNumeric);
}
});
return smallestSoFar[2];
}
console.log(FindThirdSmallestNumber(numbers));Note that implementations that sort the whole array (as other answers do) is O(N log N), while sorting here is only ever done on an array of size 3, which is significantly less complex (O(N log 3) I think, which is equivalent to O(N))
answered Nov 21 at 1:40
CertainPerformance
74.4k143659
add a comment |
1
One option would be to have a separate sorted array of the three smallest numbers so far. Whenever you run across a number smaller than the 3rd smallest (the last in the sorted array), reassign that 3rd index to the new number, and sort it again:
const numbers = [3, 2, 55, -10, -55, 5, 3, 2, 1, -5, 33, 9, -1, 4, 5];
const sortNumeric = (a, b) => a - b;
function FindThirdSmallestNumber(input) {
const [smallestSoFar, numbers] = [input.slice(0, 3), input.slice(3)];
smallestSoFar.sort(sortNumeric);
numbers.forEach((num) => {
if (num < smallestSoFar[2]) {
smallestSoFar[2] = num;
smallestSoFar.sort(sortNumeric);
}
});
return smallestSoFar[2];
}
console.log(FindThirdSmallestNumber(numbers));Note that implementations that sort the whole array (as other answers do) is O(N log N), while sorting here is only ever done on an array of size 3, which is significantly less complex (O(N log 3) I think, which is equivalent to O(N))
answered Nov 21 at 1:40
CertainPerformance
74.4k143659
add a comment |
1
1
1
One option would be to have a separate sorted array of the three smallest numbers so far. Whenever you run across a number smaller than the 3rd smallest (the last in the sorted array), reassign that 3rd index to the new number, and sort it again:
const numbers = [3, 2, 55, -10, -55, 5, 3, 2, 1, -5, 33, 9, -1, 4, 5];
const sortNumeric = (a, b) => a - b;
function FindThirdSmallestNumber(input) {
const [smallestSoFar, numbers] = [input.slice(0, 3), input.slice(3)];
smallestSoFar.sort(sortNumeric);
numbers.forEach((num) => {
if (num < smallestSoFar[2]) {
smallestSoFar[2] = num;
smallestSoFar.sort(sortNumeric);
}
});
return smallestSoFar[2];
}
console.log(FindThirdSmallestNumber(numbers));Note that implementations that sort the whole array (as other answers do) is O(N log N), while sorting here is only ever done on an array of size 3, which is significantly less complex (O(N log 3) I think, which is equivalent to O(N))
answered Nov 21 at 1:40
CertainPerformance
74.4k143659
One option would be to have a separate sorted array of the three smallest numbers so far. Whenever you run across a number smaller than the 3rd smallest (the last in the sorted array), reassign that 3rd index to the new number, and sort it again:
const numbers = [3, 2, 55, -10, -55, 5, 3, 2, 1, -5, 33, 9, -1, 4, 5];
const sortNumeric = (a, b) => a - b;
function FindThirdSmallestNumber(input) {
const [smallestSoFar, numbers] = [input.slice(0, 3), input.slice(3)];
smallestSoFar.sort(sortNumeric);
numbers.forEach((num) => {
if (num < smallestSoFar[2]) {
smallestSoFar[2] = num;
smallestSoFar.sort(sortNumeric);
}
});
return smallestSoFar[2];
}
console.log(FindThirdSmallestNumber(numbers));Note that implementations that sort the whole array (as other answers do) is O(N log N), while sorting here is only ever done on an array of size 3, which is significantly less complex (O(N log 3) I think, which is equivalent to O(N))
const numbers = [3, 2, 55, -10, -55, 5, 3, 2, 1, -5, 33, 9, -1, 4, 5];
const sortNumeric = (a, b) => a - b;
function FindThirdSmallestNumber(input) {
const [smallestSoFar, numbers] = [input.slice(0, 3), input.slice(3)];
smallestSoFar.sort(sortNumeric);
numbers.forEach((num) => {
if (num < smallestSoFar[2]) {
smallestSoFar[2] = num;
smallestSoFar.sort(sortNumeric);
}
});
return smallestSoFar[2];
}
console.log(FindThirdSmallestNumber(numbers));const numbers = [3, 2, 55, -10, -55, 5, 3, 2, 1, -5, 33, 9, -1, 4, 5];
const sortNumeric = (a, b) => a - b;
function FindThirdSmallestNumber(input) {
const [smallestSoFar, numbers] = [input.slice(0, 3), input.slice(3)];
smallestSoFar.sort(sortNumeric);
numbers.forEach((num) => {
if (num < smallestSoFar[2]) {
smallestSoFar[2] = num;
smallestSoFar.sort(sortNumeric);
}
});
return smallestSoFar[2];
}
console.log(FindThirdSmallestNumber(numbers));answered Nov 21 at 1:40
CertainPerformance
74.4k143659
answered Nov 21 at 1:40
CertainPerformance
74.4k143659
answered Nov 21 at 1:40
CertainPerformance
74.4k143659
answered Nov 21 at 1:40
CertainPerformance
74.4k143659
74.4k143659
add a comment |
add a comment |
1
This one should be a lot simpler. Also not sure about this being any faster but in the most simple/obvious cases less code = better performance.
I just sort the array ascending and get the value based on index. So with this code you can get any place; lowest, second lowest, third lowest, etc as long as your index does not go out of range.
const input = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function getLowestByRank(data, rank) {
data.sort(function(a, b){ return a - b });
return data[rank - 1];
}
console.log(getLowestByRank(input, 3))
console.log(getLowestByRank(input, 2))
console.log(getLowestByRank(input, 4))
answered Nov 21 at 1:37
Abana Clara
1,511819
add a comment |
1
This one should be a lot simpler. Also not sure about this being any faster but in the most simple/obvious cases less code = better performance.
I just sort the array ascending and get the value based on index. So with this code you can get any place; lowest, second lowest, third lowest, etc as long as your index does not go out of range.
const input = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function getLowestByRank(data, rank) {
data.sort(function(a, b){ return a - b });
return data[rank - 1];
}
console.log(getLowestByRank(input, 3))
console.log(getLowestByRank(input, 2))
console.log(getLowestByRank(input, 4))
answered Nov 21 at 1:37
Abana Clara
1,511819
add a comment |
1
1
1
This one should be a lot simpler. Also not sure about this being any faster but in the most simple/obvious cases less code = better performance.
I just sort the array ascending and get the value based on index. So with this code you can get any place; lowest, second lowest, third lowest, etc as long as your index does not go out of range.
const input = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function getLowestByRank(data, rank) {
data.sort(function(a, b){ return a - b });
return data[rank - 1];
}
console.log(getLowestByRank(input, 3))
console.log(getLowestByRank(input, 2))
console.log(getLowestByRank(input, 4))
answered Nov 21 at 1:37
Abana Clara
1,511819
This one should be a lot simpler. Also not sure about this being any faster but in the most simple/obvious cases less code = better performance.
I just sort the array ascending and get the value based on index. So with this code you can get any place; lowest, second lowest, third lowest, etc as long as your index does not go out of range.
const input = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function getLowestByRank(data, rank) {
data.sort(function(a, b){ return a - b });
return data[rank - 1];
}
console.log(getLowestByRank(input, 3))
console.log(getLowestByRank(input, 2))
console.log(getLowestByRank(input, 4))
const input = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function getLowestByRank(data, rank) {
data.sort(function(a, b){ return a - b });
return data[rank - 1];
}
console.log(getLowestByRank(input, 3))
console.log(getLowestByRank(input, 2))
console.log(getLowestByRank(input, 4))
const input = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function getLowestByRank(data, rank) {
data.sort(function(a, b){ return a - b });
return data[rank - 1];
}
console.log(getLowestByRank(input, 3))
console.log(getLowestByRank(input, 2))
console.log(getLowestByRank(input, 4))
answered Nov 21 at 1:37
Abana Clara
1,511819
edited Nov 21 at 1:45
answered Nov 21 at 1:37
Abana Clara
1,511819
answered Nov 21 at 1:37
Abana Clara
1,511819
answered Nov 21 at 1:37
Abana Clara
1,511819
1,511819
add a comment |
add a comment |
0
You can use Math.min function to determine the minimum until you find your X smallest number:
Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function FindSmallestNumber(arr, limit) {
var min = '';
for(var counter = 1; counter <= limit; counter ++) {
min = Math.min.apply(Math, arr);
arr.splice(arr.indexOf(min), 1);
}
console.log(min);
}
FindSmallestNumber(Numbers, 3); //3rd smallest number
answered Nov 21 at 1:42
Mojo Allmighty
645316
add a comment |
0
You can use Math.min function to determine the minimum until you find your X smallest number:
Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function FindSmallestNumber(arr, limit) {
var min = '';
for(var counter = 1; counter <= limit; counter ++) {
min = Math.min.apply(Math, arr);
arr.splice(arr.indexOf(min), 1);
}
console.log(min);
}
FindSmallestNumber(Numbers, 3); //3rd smallest number
answered Nov 21 at 1:42
Mojo Allmighty
645316
add a comment |
0
0
0
You can use Math.min function to determine the minimum until you find your X smallest number:
Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function FindSmallestNumber(arr, limit) {
var min = '';
for(var counter = 1; counter <= limit; counter ++) {
min = Math.min.apply(Math, arr);
arr.splice(arr.indexOf(min), 1);
}
console.log(min);
}
FindSmallestNumber(Numbers, 3); //3rd smallest number
answered Nov 21 at 1:42
Mojo Allmighty
645316
You can use Math.min function to determine the minimum until you find your X smallest number:
Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function FindSmallestNumber(arr, limit) {
var min = '';
for(var counter = 1; counter <= limit; counter ++) {
min = Math.min.apply(Math, arr);
arr.splice(arr.indexOf(min), 1);
}
console.log(min);
}
FindSmallestNumber(Numbers, 3); //3rd smallest number
answered Nov 21 at 1:42
Mojo Allmighty
645316
answered Nov 21 at 1:42
Mojo Allmighty
645316
answered Nov 21 at 1:42
Mojo Allmighty
645316
answered Nov 21 at 1:42
Mojo Allmighty
645316
645316
add a comment |
add a comment |
0
I think sorting the array is likely the fastest method, but perhaps you want avoid the built–in sort. An alternative is as Chris Li suggests: iterate over the values and just keep the 3 lowest, then return the highest of the three.
I assumed you want to avoid built-in methods, so this only uses some basic array methods and does everything else manually.
// Avoid Math.max
function getMax(arr) {
var max = -Infinity;
for (var i=0, iLen=arr.length; i<iLen; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
// If data.length < 4, just returns largest value
// Iterates over data once
function get3rdSmallest(data) {
// Helper to insert value in order
// Expects arr to be length 3 or smaller
function insertNum(arr, num) {
if (!arr.length || num < arr[0]) {
nums.unshift(num);
} else if (num > arr[arr.length-1]) {
arr.push(num);
} else {
arr[2] = arr[1];
arr[1] = num;
}
}
var num, nums = ;
if (data.length < 4) {
return getMax(data);
}
for (var i=0, iLen=data.length; i<iLen; i++) {
num = data[i];
// Insert first 3 values sorted
if (nums.length < 3) {
insertNum(nums, num);
// If num is smaller than largest value in nums,
// remove move largest and insert num
} else if (num < nums[2]){
nums.splice(-1);
insertNum(nums, num);
}
}
// Return highest (last) value in nums
return nums[2];
}
var data = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
console.log(get3rdSmallest([-4,-22])); // -4
console.log(get3rdSmallest([4,0,1,7,6])); // 4
console.log(get3rdSmallest(data)); // -5answered Nov 21 at 2:16
RobG
96.8k19103145
add a comment |
0
I think sorting the array is likely the fastest method, but perhaps you want avoid the built–in sort. An alternative is as Chris Li suggests: iterate over the values and just keep the 3 lowest, then return the highest of the three.
I assumed you want to avoid built-in methods, so this only uses some basic array methods and does everything else manually.
// Avoid Math.max
function getMax(arr) {
var max = -Infinity;
for (var i=0, iLen=arr.length; i<iLen; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
// If data.length < 4, just returns largest value
// Iterates over data once
function get3rdSmallest(data) {
// Helper to insert value in order
// Expects arr to be length 3 or smaller
function insertNum(arr, num) {
if (!arr.length || num < arr[0]) {
nums.unshift(num);
} else if (num > arr[arr.length-1]) {
arr.push(num);
} else {
arr[2] = arr[1];
arr[1] = num;
}
}
var num, nums = ;
if (data.length < 4) {
return getMax(data);
}
for (var i=0, iLen=data.length; i<iLen; i++) {
num = data[i];
// Insert first 3 values sorted
if (nums.length < 3) {
insertNum(nums, num);
// If num is smaller than largest value in nums,
// remove move largest and insert num
} else if (num < nums[2]){
nums.splice(-1);
insertNum(nums, num);
}
}
// Return highest (last) value in nums
return nums[2];
}
var data = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
console.log(get3rdSmallest([-4,-22])); // -4
console.log(get3rdSmallest([4,0,1,7,6])); // 4
console.log(get3rdSmallest(data)); // -5answered Nov 21 at 2:16
RobG
96.8k19103145
add a comment |
0
0
0
I think sorting the array is likely the fastest method, but perhaps you want avoid the built–in sort. An alternative is as Chris Li suggests: iterate over the values and just keep the 3 lowest, then return the highest of the three.
I assumed you want to avoid built-in methods, so this only uses some basic array methods and does everything else manually.
// Avoid Math.max
function getMax(arr) {
var max = -Infinity;
for (var i=0, iLen=arr.length; i<iLen; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
// If data.length < 4, just returns largest value
// Iterates over data once
function get3rdSmallest(data) {
// Helper to insert value in order
// Expects arr to be length 3 or smaller
function insertNum(arr, num) {
if (!arr.length || num < arr[0]) {
nums.unshift(num);
} else if (num > arr[arr.length-1]) {
arr.push(num);
} else {
arr[2] = arr[1];
arr[1] = num;
}
}
var num, nums = ;
if (data.length < 4) {
return getMax(data);
}
for (var i=0, iLen=data.length; i<iLen; i++) {
num = data[i];
// Insert first 3 values sorted
if (nums.length < 3) {
insertNum(nums, num);
// If num is smaller than largest value in nums,
// remove move largest and insert num
} else if (num < nums[2]){
nums.splice(-1);
insertNum(nums, num);
}
}
// Return highest (last) value in nums
return nums[2];
}
var data = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
console.log(get3rdSmallest([-4,-22])); // -4
console.log(get3rdSmallest([4,0,1,7,6])); // 4
console.log(get3rdSmallest(data)); // -5answered Nov 21 at 2:16
RobG
96.8k19103145
I think sorting the array is likely the fastest method, but perhaps you want avoid the built–in sort. An alternative is as Chris Li suggests: iterate over the values and just keep the 3 lowest, then return the highest of the three.
I assumed you want to avoid built-in methods, so this only uses some basic array methods and does everything else manually.
// Avoid Math.max
function getMax(arr) {
var max = -Infinity;
for (var i=0, iLen=arr.length; i<iLen; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
// If data.length < 4, just returns largest value
// Iterates over data once
function get3rdSmallest(data) {
// Helper to insert value in order
// Expects arr to be length 3 or smaller
function insertNum(arr, num) {
if (!arr.length || num < arr[0]) {
nums.unshift(num);
} else if (num > arr[arr.length-1]) {
arr.push(num);
} else {
arr[2] = arr[1];
arr[1] = num;
}
}
var num, nums = ;
if (data.length < 4) {
return getMax(data);
}
for (var i=0, iLen=data.length; i<iLen; i++) {
num = data[i];
// Insert first 3 values sorted
if (nums.length < 3) {
insertNum(nums, num);
// If num is smaller than largest value in nums,
// remove move largest and insert num
} else if (num < nums[2]){
nums.splice(-1);
insertNum(nums, num);
}
}
// Return highest (last) value in nums
return nums[2];
}
var data = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
console.log(get3rdSmallest([-4,-22])); // -4
console.log(get3rdSmallest([4,0,1,7,6])); // 4
console.log(get3rdSmallest(data)); // -5// Avoid Math.max
function getMax(arr) {
var max = -Infinity;
for (var i=0, iLen=arr.length; i<iLen; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
// If data.length < 4, just returns largest value
// Iterates over data once
function get3rdSmallest(data) {
// Helper to insert value in order
// Expects arr to be length 3 or smaller
function insertNum(arr, num) {
if (!arr.length || num < arr[0]) {
nums.unshift(num);
} else if (num > arr[arr.length-1]) {
arr.push(num);
} else {
arr[2] = arr[1];
arr[1] = num;
}
}
var num, nums = ;
if (data.length < 4) {
return getMax(data);
}
for (var i=0, iLen=data.length; i<iLen; i++) {
num = data[i];
// Insert first 3 values sorted
if (nums.length < 3) {
insertNum(nums, num);
// If num is smaller than largest value in nums,
// remove move largest and insert num
} else if (num < nums[2]){
nums.splice(-1);
insertNum(nums, num);
}
}
// Return highest (last) value in nums
return nums[2];
}
var data = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
console.log(get3rdSmallest([-4,-22])); // -4
console.log(get3rdSmallest([4,0,1,7,6])); // 4
console.log(get3rdSmallest(data)); // -5// Avoid Math.max
function getMax(arr) {
var max = -Infinity;
for (var i=0, iLen=arr.length; i<iLen; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
// If data.length < 4, just returns largest value
// Iterates over data once
function get3rdSmallest(data) {
// Helper to insert value in order
// Expects arr to be length 3 or smaller
function insertNum(arr, num) {
if (!arr.length || num < arr[0]) {
nums.unshift(num);
} else if (num > arr[arr.length-1]) {
arr.push(num);
} else {
arr[2] = arr[1];
arr[1] = num;
}
}
var num, nums = ;
if (data.length < 4) {
return getMax(data);
}
for (var i=0, iLen=data.length; i<iLen; i++) {
num = data[i];
// Insert first 3 values sorted
if (nums.length < 3) {
insertNum(nums, num);
// If num is smaller than largest value in nums,
// remove move largest and insert num
} else if (num < nums[2]){
nums.splice(-1);
insertNum(nums, num);
}
}
// Return highest (last) value in nums
return nums[2];
}
var data = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
console.log(get3rdSmallest([-4,-22])); // -4
console.log(get3rdSmallest([4,0,1,7,6])); // 4
console.log(get3rdSmallest(data)); // -5answered Nov 21 at 2:16
RobG
96.8k19103145
answered Nov 21 at 2:16
RobG
96.8k19103145
answered Nov 21 at 2:16
RobG
96.8k19103145
answered Nov 21 at 2:16
RobG
96.8k19103145
96.8k19103145
add a comment |
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53404068%2ffinding-third-smallest-number-in-a-given-set-of-numbers-with-least-time-complexi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
What do you mean by less time complexity?
– Abana Clara
Nov 21 at 1:33
1
For the general case (kth smallest) you can use a max heap with a resulting time complexity of O(n log k).
– slider
Nov 21 at 1:34
if you only need the 3rd smallest you can use 3 variables to keep track of the 3 smallest numbers and find the 3rd smallest in linear time..
– Chris Li
Nov 21 at 1:37
Numbersis not a good variable name given it's similarity to the built–in Number object. Your approach seems to be a bubble sort, which is very inefficient and may require multiple passes to fully order the array (basically you keep iterating until nothing moves). I think thei -= 1is redundant, it just means the same to values are tested again on the next iteration.– RobG
Nov 21 at 1:41
Can you please explicitly state what the time complexity of your above algorithm is?
– slider
Nov 21 at 1:49