Remove Max Value from Simply-Connected List

Remove max value from simply-connected list

#include <cstdio>
#include <iostream>

struct Stack
{
    int info;
    Stack *next;
    // added just to easy initialization
    Stack(int _info, Stack *_next) : info(_info), next(_next) {}
} *top;

void delMaxValue(Stack *&head) 
{
    // first - find MaxValue in the list
    // as you can see, i save pointer to the previous element in the list
    Stack* max_prev = nullptr;
    Stack* max = head;
    for(Stack *i_prev = nullptr, *i = head; i; i_prev = i, i = i->next) {
         if (max->info < i->info) {
             max_prev = i_prev;
             max = i;
         }
    }
    // max has the maximum value and max_prev is the element before max in the list
    // now we remove max
    if (max_prev == nullptr) {
        // max has no prev, so max is the head of the list. We assign the new head
        head = max->next;
     } else {
        max_prev->next = max->next;
        max->next = NULL;
     }
}

void printStack(Stack *head) {
    std::cout << "Priting " << head << std::endl;
    for(Stack *i = head; i; i = i->next) {
        std::cout << i << " " << i->info << std::endl;
    }
}

int main()
{
    Stack *head = new Stack(1, new Stack(15, new Stack(10, nullptr)));
    printStack(head);
    delMaxValue(head);
    printStack(head);
    return 0;
}

You may interest yourself in list helping macros from bsd, now available in glibc, newlib, openbsd etc., see here.

Dropping max value in list, keeping duplicates

You can pass maximum value in the list to list.remove method; it removes the first occurrence of the value passed.

>>> my_list.remove(max(my_list))
>>> my_list
[11, 10]

PS: It's a mutable operation, so it changes the original list.

Above works only when there's repeated maximum, you can combine it with what you have done:

if my_list.count(max(my_list)) == 1:
    my_list = [i for i in my_list if i!=max(my_list)]
else:
    my_list.remove(max(my_list))  

max value of list without max() method

max = list[0]
for x in list:
    if x > max:
        max = x
print max

In this example, we initialize the max value to the first element. Then we iterate through the list, and if we find a larger value than the current max, we assign that value to max. At the end, we should have the largest value, which we print.

Comparator to get the maximum value in Linked List with exclude the first element of the Linked List from the comparison

You can create a sublist from the original list (it is just a view, it doesn't copy all the elements).

So you can change:

System.out.println("Max value in this element " + Collections.max(PathList,cmp));

To:

LinkedList<HashMap<Integer, Integer>> pathListWithoutFirst = PathList.subList(1, PathList.size());
System.out.println("Max value in this element " + Collections.max(pathListWithoutFirst, cmp));

How to use a LINQ in order to remove Min and Max value in List

You should be using where.

from pair in temp
where pair < temp.Max() && pair > temp.Min()
select pair

Your current approach will select whether the values are in range, not filter them. That's what the where clause is for.

How to use list comprehension for excluding maximum value in a list

Can try:

l = [1,3,5,8,9]
l_copy = l.copy() # just not to mutate the original list
l_copy = l_copy.remove(max(l_copy))
res = sum(l_copy)

Explain:

max(l_copy) # return the max value in l
l_copy = l_copy.remove(max(l_copy)) # remove the max value of the list

sum(l) # sum all list except the max value

Pay attention to an input of empty list..

Remove all occurrences of a value from a list?

Functional approach:

Python 3.x

>>> x = [1,2,3,2,2,2,3,4]
>>> list(filter((2).__ne__, x))
[1, 3, 3, 4]

or

>>> x = [1,2,3,2,2,2,3,4]
>>> list(filter(lambda a: a != 2, x))
[1, 3, 3, 4]

Python 2.x

>>> x = [1,2,3,2,2,2,3,4]
>>> filter(lambda a: a != 2, x)
[1, 3, 3, 4]

How to use a LINQ : If there are several min and max values, just remove only one min and max value in List

Sorting and removing first and last value should work just fine. You can do it like that:

var tempWithoutMinAndMax = temp.OrderBy(m => m.value).Skip(1).Take(temp.Count-2);

//Edit: I was curious about Rashid Ali's solution (below) so I decided to perform a quick test. I created a list with 10 000 elements:

var list = new List<KeyValuePair<int, int>>();
for(int i=0;i<10000;i++)
{
    list.Add(new KeyValuePair<int, int>(i,random.Next()));
}

Then i removed single Min and Max element from the list using both methods and measured the time. My test code:

Stopwatch watch = new Stopwatch();
watch.Start();
var ver1 = list.OrderBy(m => m.Value).Skip(1).Take(list.Count - 2).ToList();
watch.Stop();
var ver1time = watch.ElapsedMilliseconds;
watch.Reset();
watch.Start();
list.Remove(list.Where(x => x.Value == list.Max(y => y.Value)).First());
list.Remove(list.Where(x => x.Value == list.Min(y => y.Value)).First());
watch.Stop();
var ver2time = watch.ElapsedMilliseconds;
Console.WriteLine("First method (order by): {0}ms\nSecond method (remove): {1}ms",
ver1time,ver2time);

Result: First method (order by): 11ms, Second method (remove): 3424ms
I ran this test a couple of times and all results were similar. I didn't check what IL code earch method produces, but clearly using OrderBy outperforms combining Remove, Where and Min/Max

How to write a query to delete everything except maximum value grouped by an ID?

After our discussion, I understand that you aimed to select many rows of data which respects the filter id and max(value). Therefore, I can suggest you the following script:

SELECT
  DISTINCT a.*
FROM
  `test-proj-261014.sample.id_value` a
RIGHT JOIN (
  SELECT
    id,
    MAX(value) AS max_val
  FROM
    `test-proj-261014.sample.id_value`
  GROUP BY
    id
  ORDER BY
    id) b
ON
  a.id = b.id
  AND a.value = b.max_val
WHERE
  a.value IS NOT NULL
ORDER BY
  id;

Not that I use SELECT DISTINCT, which will not select duplicated data. In addition, due to the possibility of the existence of null values, I added the consition***WHERE a.value IS NOT NULL***, which will not select the rows that do not respect the condition.

The above query should solve the problem, however if you find any discrepancy with the expected amount of rows, I encourage you explore your data set and detect the reason why there are extra or less rows. You can use different types of joins to do so, one example would be the following query:

SELECT
  a.*
FROM
  `test-proj-261014.sample.id_value` a
LEFT JOIN (
  SELECT
    id,
    MAX(value) AS max_val
  FROM
    `test-proj-261014.sample.id_value`
  GROUP BY
    id
  ORDER BY
    id) b
ON
  a.id = b.id
  AND a.value = b.max_val
WHERE
  b.max_val IS NULL
ORDER BY
  id;

This query retrieves all the values which are not present in the final output generated by the first query. This would help you understand better the data you are dealing with.

I hope it helps.

---

Related Topics